How large can $X\subset \mathbb{F}_2^{10}$ be without solutions to $x_1+\cdots+x_n=0$ for $n\le4$?

Question

Suppose some 10-bit binary numbers, $X\subset \mathbb{F}_2^{10}$. I'd like to construct $X$ as large as possible with no solutions to $x_1+\cdots+x_n=0$ for $x_i\in X$ and $n\le 4$. Explicitly,

• The condition $n=1$ simply requires that $0\not\in X$.
• And $n=2$ simply requires the elements of $X$ all distinct (which we knew already as $X$ is defined to be a subset).
• But $n=3$ requires equivalently that no $x\in X$ is the sum of two other elements in $X$.
• And lastly, $n=4$ requires equivalently that no pair of elements in $X$ have the same sum as any other such pair. I.e. that $x_1+x_2\not= x_3+x_4$.

The latter two in particular imply all elements and pair-wise sums in $X$ distinct. Of course, there are $$\binom{|X|}{1}+\binom{|X|}{2}=\frac{|X|\big(|X|+1\big)}{2}$$ such values. As $\mathbb{F}_2^{10}$ only has $2^{10}=1024$ values, it follows that $|X|\le 44$ since $\frac{46(46-1)}{2}=1035$ would imply more distinct values in $\mathbb{F}_2^{10}$ than elements.

The trouble is, the largest such $X$ I could find with computer search had $30$ elements. After hours of toying with the problem over the past weeks, I couldn't even rule out $|X|=44$. I feel like Ramsey theory and a graph formulation could be applicable here. I did, at least manage to prove that any $X$ with $44$ elements would require at least $1017$ distinct values in $\mathbb{F}_2^{10}$ rather than $\binom{44}{1}+\binom{44}{2}=990$ achieved by the foregoing argument. But even this wasn't straightforward.

Is there any way to bridge the gap between the best in practice and the best in theory here?

Answer 1

I adapted the simulated annealing code I wrote for What's the smallest set that covers $\mathbb{B}^n$ with at most one XOR operation?. Here’s the new code. The best I could find for $10$ bits was a set of $33$:

0011000011 0101100101 0011101111 1011011000 1110001010
0111111011 1110111111 1110101111 1110011111 1011111111
1010101000 0000111011 0001001010 1000110100 1001010010
0101100010 0100000110 0010110110 0001111000 0101000110
1111000011 1000111101 1011010101 0100011100 0111000010
1011000011 0010111001 0101000011 0010100001 1101100000
1101001101 1001010011 0111010000

With a set of $34$, I never got below $12$ duplicated sums with several slow annealing runs, so I suspect there’s no admissible set of $34$.

I can confirm the values posted for $1$ through $8$ bits in @RobPratt’s comment, $1,2,3,5,6,8,11,17$. For $9$ bits, the best I found was a set of $23$, so there’s a relatively large step from $23$ to $33$ going from $9$ bits to $10$.