# Cardinality of certain subsets in vector spaces over finite fields

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.

• A title with information on the subject would be maybe more useful than one just conveying your opinion on the value of the question – YCor May 2 at 22:27
• What is a non trivial lower bound... Are you sure you did not mean "upper bound"? – fedja May 2 at 22:57
• 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)? – LSpice May 3 at 0:11
• It must mean a lower bound on the maximum size of such an $A$. – Zach Teitler May 3 at 2:30
• 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. – Martin Sleziak May 3 at 8:55

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}$$.

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.

• 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. – dvitek May 3 at 6:04