For a finite set $S$ of $n$ elements, say a weight function is a function $f \colon S \to \mathbb{R}$. For any subset $T \subseteq S$, define $f(T) = \sum \_{x \in T} f(x)$. Define two weight functions $f\_1, f\_2$ on the same set $S$ to be *equivalent* if $f\_1(T\_1) \leq f\_1(T\_2) \Leftrightarrow f\_2(T\_1) \leq f\_2(T\_2)$ for all sets $T\_1, T\_2 \subseteq S$. 


How many non-equivalent weight functions are there on a set of $n$ elements, asymptotically as a function of $n$? It follows from a [result of Frank and Tardos](https://link.springer.com/article/10.1007/BF02579200) (Thm 3.3) that there are at most $2^{O(n^4)}$ distinct weight functions, but I am interested to know what the optimal degree is of the polynomial in the exponent.



Number of nonequivalent weight functions on a set of $n$ elements
It turns out my question is answered in a recent paper by [Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, and Shmuel Onn](https://arxiv.org/abs/1904.01361) on the complexity of integer programming. Letting $w \in \mathbb{R}^n$ be the vector of weights, the weight of a subset $S' \subseteq S$ can be written by letting $x\_{S'}$ be the $0/1$-characteristic vector of $S'$, so that the weight of $S'$ becomes the inner product $w \cdot x\_{S'}$. 


Theorem 65 in the cited paper shows that for any linear function $f(x) = w \cdot x$ for $x \in \{0,1\}^n$, there is an equivalent weight function $g(x) = w' \cdot x$ such that $w' \in \{- n(12n)^n, \ldots, n(12n)^n\}$, that is, each weight is an integer whose absolute value is $n \cdot n^{O(n)}$. Hence each weight function has a representation with each of the $n$ weights belonging to this range, giving an upper-bound of at most $(1+2n \cdot n^{O(n)})^n = 2^{O(n^2 \log n)}$ nonequivalent weight functions.


