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

$\begingroup$ May $c$ depend on $k$? $\endgroup$ – Ilya Bogdanov May 9 at 9:54

$\begingroup$ Yes, c may depend on $k.$ And, I conjecture that $c = 1/k$ is one of the suitable constant. $\endgroup$ – 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^{2k1})$ 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,2k1$ 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,2k1$. 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^{r1}, $$ and likewise $\beta'/\beta = \sum_{r=1}^\infty p_r(B) \, t^{r1}$. These Taylor expansions agree through the $t^{2k1}$ 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

1$\begingroup$ Does this work over arbitrary characteristic, if I replace $1, 3, \dots, 2k1$ 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.) $\endgroup$ – Sean Eberhard May 10 at 10:35

1$\begingroup$ 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 functionfield 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 threeelement subsets of $\bf C$, except those with $p_1 = 0$ (for which $p_4 = p_2^2/2$). $\endgroup$ – Noam D. Elkies May 10 at 13:45