6
$\begingroup$

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

$\endgroup$
  • $\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
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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.) $\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 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$). $\endgroup$ – Noam D. Elkies May 10 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.