Distinct Sums Modulo n and Tree Embeddings

NEW

Problem: Reconstructed statement: let $[k]=\{1,\dots,k\}$, let $\mathbb Z_n$ be the cyclic group, call $f:[k]^2\to\mathbb Z_n$ alternating if $f(i,i)=0$ and $f(j,i)=-f(i,j)$. For $\pi\in S_k$, set

$$d_\pi(i,j)=\pi(i)-\pi(j)\in\mathbb Z_n .$$

The conjecture asserts: if $k<n$, then for every alternating $f$ there is $\pi\in S_k$ such that

$$d_\pi(i,j)\ne f(i,j)\quad\text{for all }i\ne j.$$

This is the natural reading from the distinct-sums context, since distinctness of $a_i+\pi(i)$ is equivalent to avoiding prescribed differences $\pi(i)-\pi(j)=a_j-a_i$.

Result: The literal conjecture is false.

Take $k=3$, $n=4$, and define

$$f(i,i)=0,\qquad f(i,j)=2\in\mathbb Z_4 \quad (i\ne j).$$

This is alternating, because $-2\equiv 2\pmod 4$.

For any $\pi\in S_3$, the values $\pi(1),\pi(2),\pi(3)$ are exactly $1,2,3$. Hence two vertices, say $i,j$, receive the values $1$ and $3$. Therefore

$$\pi(i)-\pi(j)\equiv \pm 2\equiv 2\pmod 4.$$

Since $f(i,j)=2$, the required inequality fails. Thus no such permutation exists.

More generally, for every even $n=2m$ and every $m<k<n$, the constant off-diagonal function $f(i,j)=m$ is alternating and gives the same obstruction, since $[k]$ contains two numbers differing by $m$.

A natural repair is to replace $k<n$ by $2k\le n+1$, equivalently $n\ge 2k-1$. This removes the wraparound/two-torsion obstruction. In that range the repaired statement is true by the standard polynomial-method argument: for $i<j$, choose the unique integer representative $c_{ij}\in[-(k-1),k-1]$, when it exists, of $f(i,j)$, and otherwise choose any integer outside this interval. Consider

$$P(x_1,\dots,x_k)=\prod_{i<j}(x_i-x_j)(x_i-x_j-c_{ij}).$$

The coefficient of $\prod_i x_i^{k-1}$ is the coefficient of the same monomial in $\prod_{i<j}(x_i-x_j)^2$, namely

$$(-1)^{\binom{k}{2}}k!\ne 0$$

over $\mathbb Q$. By Alon’s Combinatorial Nullstellensatz, $P$ is nonzero at some point of $\{1,\dots,k\}^k$. The Vandermonde factors force the coordinates to be distinct, hence a permutation, and the second factors give the required avoidance.

Citation: The counterexample above is elementary. The repaired range $2k\le n+1$ is exactly the range proved in Kézdy–Snevily, “Distinct Sums Modulo $n$ and Tree Embeddings,” Combinatorics, Probability and Computing 11 (2002), 35–42, using the polynomial method/Combinatorial Nullstellensatz.