5
$\begingroup$

Assume that you have an $n$-dimensional vector space over a finite field (therefore the number of elements in the vector space is finite) and $F$ is a subset of this vector space which contains $m$ elements. Let's $A$ is a subset of this vector space such that the intersection of $A+A$ and $F$ is empty.

The question is: What is a non trivial lower bound for the cardinality of $A$?

Thank you.

$\endgroup$
  • 35
    $\begingroup$ A title with information on the subject would be maybe more useful than one just conveying your opinion on the value of the question $\endgroup$ – YCor May 2 at 22:27
  • 10
    $\begingroup$ What is a non trivial lower bound... Are you sure you did not mean "upper bound"? $\endgroup$ – fedja May 2 at 22:57
  • 6
    $\begingroup$ As @fedja says, clearly $A = \emptyset$ will satisfy your condition, so it is hard to imagine a non-trivial lower bound. In fact I find it hard to read the question overall. Should it be: "What is the best upper bound [in terms of $F$? Independent of $F$?] on the cardinality of a subset $A$ of $V$ such that $A + A \cap F = \emptyset$" (where $V$ is your chosen vector space)? $\endgroup$ – LSpice May 3 at 0:11
  • 2
    $\begingroup$ It must mean a lower bound on the maximum size of such an $A$. $\endgroup$ – Zach Teitler May 3 at 2:30
  • 5
    $\begingroup$ Here is a copy of the question on Mathematics Stack Exchange: Cardinality of certain subsets in vector spaces over finite fields. You can find a very reasonable advice about cross-posting in this answer. $\endgroup$ – Martin Sleziak May 3 at 8:55
8
$\begingroup$

Consider the addition Cayley graph $\Gamma$ induced by $F$ on $\mathbb Z_2^n$ (which is the graph with the vertex set $\mathbb Z_2^n$, with the vertices $u,v\in\mathbb Z_2^n$ adjacent whenever $u+v\in F$). A set $A$ with $(A+A)\cap F=\emptyset$ is an independent set in $\Gamma$. Since $\Gamma$ is regular of degree $|F|$, it has an independent set of size at least $2^n/(|F|+1)$.

In general, this bound is best possible: it is attained when $F$ is a subgroup of $\mathbb Z_2^n$ with the zero element removed (so that $|F|=2^k-1$, where $k$ is the rank of $F$), and $A$ contains a unique element from each $F$-coset.

Better bounds can be given if some information about the set $F$ is available. Say, if $F=\{f_1,\dotsc, f_m\}$ is an independent set, then one can find a subgroup $H<\mathbb Z_2^n$ such that $\mathbb Z_2^n=\langle F\rangle\oplus H$, and take $$ A := \{ c_1f_1+\dotsb+c_mf_m+h\colon c_1+\dotsb+c_m=0,\ h\in H \} $$ to have $|A|=2^{n-1}$.

$\endgroup$
3
$\begingroup$

For $V$ a vector space over ${\mathbb Z}/2{\mathbb Z}$, the non-zero points of $V$ form a projective space in which every line has three points, and the sum of any two points (thought of as elements of $V$) is equal to the third point on the line they share.

So for $A+A$ to avoid $F$, you can take the union of a) all lines that avoid $F$, b) either of the two remaining points from any line that has exactly one point in $F$, and c) the remaining point from any line that has exactly two points in $F$, and d) the zero vector if it's not in $F$. You might have to prune this down further, but clearly you can't do any better, so this at least gives an upper bound. I don't claim it's necessarily a very good one.

$\endgroup$
  • $\begingroup$ The number of lines that have either one or two points in $F$ is exactly $|F|*(|V|-|F|)$, so the sum of (b) and (c) alone is always at least $|V|-1$ before accounting for cancellation. Thus this bound doesn't seem to be particularly useful without more work, though I may have missed something as it's late. $\endgroup$ – dvitek May 3 at 6:04

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.