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

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$$ ?

• May $c$ depend on $k$? – Ilya Bogdanov May 9 at 9:54
• Yes, c may depend on $k.$ And, I conjecture that $c = 1/k$ is one of the suitable constant. – Nguyễn Văn Thế May 9 at 12:29

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
• Does this work over arbitrary characteristic, if I replace $1, 3, \dots, 2k-1$ with the first $k$ positive integers $m_1, \dots, m_k$ not divisible by $\text{char}\,F$? In other words, the question is whether $F(p_{m_1}, \dots, p_{m_k})$ is equal to the field of symmetric rational functions over $F$. I have checked this in a few small cases from Newton's identities. (I wonder what general conditions on $m_1, \dots, m_k$ suffice for this.) – Sean Eberhard May 10 at 10:35
• Good question; I expect it works, but I don't have a proof (except when char$(F) > k$). NB It's not quite the same question as the one about the function fields. On the one hand, inseparable proper extensions can be OK (e.g. in characteristic $2$, use $p_2 = p_1^2$ istead of $p_1$). On the other, the function-field condition only promises that $\{p_{m_i}(A) : 1 \leq i \leq k \}$ characterize $A$ generically, and there might be exceptional loci. For example, $p_1,p_2,p_4$ characterize three-element subsets of $\bf C$, except those with $p_1 = 0$ (for which $p_4 = p_2^2/2$). – Noam D. Elkies May 10 at 13:45