Does this combinatorical condition characterize the (kernels of) non-degenerate quadratic forms $q:V\to \mathbb{F}_2$?

61 Views Asked by At

Let $V$ be an finite-dimensional vector space over $\mathbb{F}_2$ and let $f:{V\choose 2}\to V$ be the addition map defined by $f(\{x,y\})=x+y$. We are looking for subsets $X\subseteq V$ for which there exists an $n\in\mathbb{Z}_{\ge 0}$ with $$\#f_{{X\choose 2}}^{-1}(a)=n\quad\text{ for all $a\in V\setminus\{0\}$}.$$ Note the following:

  • If $X$ is such a subset, so is $V\setminus X$.
  • All $X$ with $\#X\in\{0,1\}$ suffice, so by the previous point, all $X$ with $\#X\in\{0,1,2^r,2^r-1\}$ do too.

It turns out that when $\dim(V)$ is odd, these are the only such subsets $X$, and when $\dim(V)=2d$ is even, any other such $X$ and $n$ must satisfy $$\#X=2^{d-1}(2^d\pm 1),\quad n=2^{d-2}(2^{d-1}\pm 1).$$ When I showed my undergraduate thesis supervisor this, he went 'of course!', and proceeded to show me an example, which we later generalized to the following.

Lemma: Let $q:V\to\mathbb{F}_2$ be a non-degenerate quadratic form, then both $\ker(q)$ and $V\setminus \ker (q)$ are subsets of $V$ satisfying the conditions described above.

The proof is a bit long to write down in its entirety here, but the idea is to look at a subset $X$ as an element of the group algebra $\mathbb{C}[V]$, extend the characters of the abelian group $V$ to ring homomorphisms $\mathbb{C}[V]\to \mathbb{C}$ and then find necessary and sufficient conditions on these 'character values' of $X$. For $X=\ker q$ the character values can be explicitly computed by looking at the dual $V^*$ (so the 'additive characters') and constructing an explicit isomorphism $V\to V^*$ using $q$. (All 'standard stuff' and 'the first thing you look at' according to my supervisor, but it took me my entire thesis...)

Question: Do there exist any other such subsets $X\subseteq V$ when $\dim(V)$ is even?


If the answer is 'no', I can see two approaches. The first is to take $X$ with $\#X\not\in\{0,1,2^r,2^r-1\}$ and assume WLOG that $0\not\in X$. Then we need to show that $1_X$ is a non-degenerate quadratic form. Bilinearity of $(x,y)\mapsto 1_X(x+y)+1_X(x)+1_X(y)$ is the hard part and is equivalent to showing that $2\mid \#(X\cap W)$ for all subspaces $W\subseteq V$ of dimension $3$.

Another approach is to first construct a non-degenerate quadratic form on $V^*$, or the character group $\hat{V}$ if you want. Here, bilinearity turns out to be equivalent to $2^{\dim(V)/2-2}\mid \#(X\cap W)$ for all subspaces of codimension $3$. (We can prove unconditionally that $2^{\dim(V)/2-3}\mid \#(X\cap W)$)

If the answer is 'yes', letting a computer look for counterexamples seems the easiest way to go. However, I've already proved there exist no other $X$ for $\dim(V)\in\{2,4\}$, and for $\dim(V)=6$, even if we note that WLOG $X$ contains $0$ and a basis, this leaves us to check ${57\choose 21}$ subsets.

1

There are 1 best solutions below

1
On BEST ANSWER

The sets you are looking for are called difference sets. From Wikipedia:

In combinatorics, a $(v,k,\lambda)$ difference set is a subset $D$ of size $k$ of a group $G$ of order $v$ such that every nonidentity element of $G$ can be expressed as a product $d_{1}d_{2}^{{-1}}$ of elements of $D$ in exactly $\lambda$ ways.

So your $X$ would be a $(2^{n}, |X|, 2n)$ difference set of the group $(V,+)$ (here $d_{1}d_{2}^{-1} = d_{1}-d_{2} = d_{1}+d_{2}$, since your group operation is addition and your field has characteristic 2). (side note: In difference set terminology, $a-b$ and $b-a$ will be counted as separate differences; here in characteristic 2, they are the same and you are only counting it once. This is why the $\lambda$ parameter is twice your $n$ value.)

Furthermore, such a difference set will give a symmetric block design with the same parameters. It is well known that a necessary condition for a symmetric $(v,k,\lambda)$ design set to exist is that $\lambda(v-1) = k(k-1)$, this gives $$(2n)(2^{2d}-1) = |X|(|X|-1).$$

You may be able to look on Google Scholar to find results on the known examples of symmetric designs with parameters $(64,28,12)$ or $(64,36,20)$, and figuring out if any of them are realizable as difference sets of $(\mathbb{F}_{2}^{6}, +)$. It looks like, in particular, there are many such designs for $(64,28,12)$.