# Number of nonequivalent weight functions on a set of $n$ elements

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 (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.

• There's an obvious lower bound of $n!$ since every ordering of the singleton sets is obviously achievable. – Tony Huynh Nov 22 '19 at 12:32
• Are there any exact counts for small $n$? I see that if we restrict $|T_1|=|T_2|=2$, then we will get OEIS A231074 or alike. – Max Alekseyev Dec 3 '19 at 21:41

You are asking for the number $$T_n$$ of threshold functions on the set $$\{-1,1\}^n$$. According to https://arxiv.org/pdf/1903.06595.pdf (Section 1.2), Zuev showed that $$\log_2T_n\sim n^2$$.
• Thanks for the reference. While I agree that the number of non-equivalent weight functions is at least the number of threshold functions, I don't see the other direction of the equivalence. How would you map each weight function $f$ to a threshold function $g$, so that non-equivalent weight functions map to different threshold functions? The obvious way seems to be picking a threshold value $t$ and letting $g(S) = 1$ iff $w(S) \geq t$, but then functions which are non-equivalent for subsets of weight less than $t$, may get mapped to the same threshold function. – Bart Jansen Nov 22 '19 at 15:31
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 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.