Maximum size of $k$-Sidon set over $\mathbb{F}_2^n.$

Question

Fix $k \in \mathbb{N}$, $k \ge 2.$ Does there exist a subset $A \subset \mathbb{F}_2^n$ such that $|A| \ge c 2^{n/k}$ with some absolutely positive constant $c,$ and satisfying $$ a_1 + a_2 + \dots + a_k \neq b_1 + b_2 + \dots + b_k $$ for every pair of distinct $k$-element subsets $\{a_1,...,a_k\} \neq \{b_1,...,b_k\}$ of $A$ ?

Answer 1

Yes, such $A$ exist for all $k$, and one can even take $c=1/2$ independent of $k$.

It is enough to prove that if $n=km$ for some integer $m$ then there exists such a subset $A$ of size $2^m$, because $A$ will then work for each $n \in [km, k(m+1))$, and $2^{n/k} < 2^{m+1}$ for all such $n$.

Identify ${\bf F}_2^n$ with the vector space $F^k$ where $F$ is a finite field of $2^m$ elements. (Alas I cannot use the usual $k$ for such a field . . .) Let $A$ consist of all vectors $(a,a^3,a^5,\ldots,a^{2k-1})$ with $a \in F$. The desired result will then follow once we prove:

Proposition. Let $A = \{a_1,\ldots,a_k\}$ and $B = \{b_1,\ldots,b_k\}$ be any $k$-element subsets of a field $F$ of characteristic $2$. If $\sum_{j=1}^k a_j^r = \sum_{j=1}^k b_j^r$ for each $r=1,3,5,\ldots,2k-1$ then $A=B$.

Proof: For any finite subset $S$ of $F$ and any integer $r \leq 0$ define $p_r(S) = \sum_{s \in S} s^k$. We thus assume that $p_r(A)=p_r(B)$ for each $r=1,3,5,\ldots,2k-1$. Since $x \mapsto x^2$ is a field homomorphism, we have $p_{2r}(S) = p_r(S)^2$, so our hypothesis implies that in fact $p_r(A)=p_r(B)$ for all positive integers $r \leq 2k$. Now let $\alpha,\beta \in F[t]$ be the polynomials $\alpha = \prod_{j=1}^k (1 + a_j t)$, $\beta = \prod_{j=1}^k (1 + b_j t)$. Then $\alpha'/\alpha$ has Taylor expansion $$ \sum_{j=1}^k \frac{a_j}{1 + a_j t} = \sum_{j=1}^k (a_j + a_j^2 t + a_j^3 t^2 + a_j^4 t^3 + \cdots) = \sum_{r=1}^\infty p_r(A) \, t^{r-1}, $$ and likewise $\beta'/\beta = \sum_{r=1}^\infty p_r(B) \, t^{r-1}$. These Taylor expansions agree through the $t^{2k-1}$ term, so $\alpha'/\alpha - \beta'/\beta = O(t^{2k})$; since $\deg(\alpha' \! \beta - \alpha \beta') < 2k$, this implies that $\alpha'/\alpha = \beta'/\beta$. Therefore $(\alpha/\beta)' = 0$, so $\alpha / \beta \in F(t^2)$. Since $A$ and $B$ may not have repeated elements it follows that $\alpha / \beta$ is a constant, whence $A=B$ as claimed. QED