# Finding a perfect matching of $\mathbb{F}_{2}^{n}$ with prescribed
differences

Benedek Kovács ELTE Linear Hypergraphs Research Group, Eötvös Loránd
University, Budapest, Hungary. Email address<EMAIL_ADDRESS>
(October 26, 2023)

###### Abstract

We consider the following question by Balister, Győri and Schelp: given
$2^{n-1}$ nonzero vectors in $\mathbb{F}_{2}^{n}$ with zero sum, is it always
possible to partition the elements of $\mathbb{F}_{2}^{n}$ into pairs such
that the difference between the two elements of the $i$-th pair is equal to
the $i$-th given vector for every $i$? An analogous question in
$\mathbb{F}_{p}$, which is a case of the so-called "seating couples" problem,
has been resolved by Preissmann and Mischler in 2009. In this paper, we prove
the conjecture in $\mathbb{F}_{2}^{n}$ in the case when the number of distinct
values among the given difference vectors is at most $n-2\log n-1$, and also
in the case when at least a fraction $\frac{1}{2}+\varepsilon$ of the given
vectors are equal (for all $\varepsilon>0$ and $n$ sufficiently large based on
$\varepsilon$).
Keywords: binary vector spaces, seating couples, prescribed differences,
functional batch code, graph colourings

##  1 Introduction

We consider the following conjecture of Balister, Győri and Schelp [1] from
2008:

######  Conjecture 1.1 (Main conjecture).

Let $n\geq 2$ be an integer and $m=2^{n-1}$. If the nonzero difference vectors
$\boldsymbol{d}_{1}$, $\boldsymbol{d}_{2}$, …, $\boldsymbol{d}_{m}$ are given
in $\mathbb{F}_{2}^{n}$ such that
$\sum\limits_{i=1}^{m}\boldsymbol{d}_{i}=\boldsymbol{0}$ (and the
$\boldsymbol{d}_{i}$’s are not necessarily distinct), then
$\mathbb{F}_{2}^{n}$ can be subdivided into disjoint pairs
$\\{\boldsymbol{a}_{i},\boldsymbol{b}_{i}\\}$ ($1\leq i\leq m$) such that
$\boldsymbol{a}_{i}-\boldsymbol{b}_{i}=\boldsymbol{d}_{i}$ holds for every
$i$.

Here and throughout the article, $\mathbb{F}_{q}$ denotes the $q$-element
field where $q$ is a prime power, and $\mathbb{F}_{q}^{n}$ denotes the vector
space of dimension $n$ over $\mathbb{F}_{q}$.

In the same year, Bacher has independently posed another analogous version of
this question, where instead of $\mathbb{F}_{2}^{n}$, we partition the
elements of $\mathbb{F}_{p}\setminus\\{0\\}$ into pairs, where $p$ is an odd
prime, and there is no restriction on the sum of the given (nonzero)
differences. For this case, Preissmann and Mischler gave a positive answer
[12]; their method relies on summing the values of an appropriate multivariate
polynomial over $\mathbb{F}_{p}$.

######  Theorem 1.2 (Preissmann, Mischler).

Let $p$ be an odd prime and $M=\frac{p-1}{2}$. If in $\mathbb{F}_{p}$, the
nonzero differences $d_{1},d_{2},\dots,d_{M}$ are given, then
$\mathbb{F}_{p}\setminus\\{0\\}$ can be partitioned into disjoint pairs
$\\{a_{i},b_{i}\\}$ ($1\leq i\leq M$) such that $a_{i}-b_{i}=d_{i}$ for each
$i$.

Later, Kohen and Sadofschi [9] gave a new proof of this claim using the
Combinatorial Nullstellensatz.

The statement can also be investigated for other cyclic groups as well. In the
ring $\mathbb{Z}_{n}$ of mod $n$ residue classes, let $\mathbb{Z}_{n}^{*}$
denote the set of units, i.e. the elements coprime to $n$. The following
conjecture of Adamaszek pertaining to cyclic groups of even order has been
proven by Kohen and Sadofschi [10]:

######  Theorem 1.3 (Kohen, Sadofschi).

Let $n=2M$ be a positive even number. If the elements
$d_{1},d_{2},\dots,d_{M}\in\mathbb{Z}_{n}^{*}$ are arbitrarily given, then
$\mathbb{Z}_{n}$ can be partitioned into disjoint pairs $\\{a_{i},b_{i}\\}$
such that $a_{i}-b_{i}=d_{i}$ for each $i$.

For newer results on this case, see [11]. The following conjecture of Karasev
and Petrov [8] is the adaptation of this claim to cyclic groups of odd order:

######  Conjecture 1.4 (Karasev, Petrov).

Let $n=2M+1$ be a positive odd number. If the elements
$d_{1},d_{2},\dots,d_{M}\in\mathbb{Z}_{n}^{*}$ are arbitrarily given, then
$\mathbb{Z}_{n}\setminus\\{0\\}$ can be partitioned into disjoint pairs
$\\{a_{i},b_{i}\\}$ such that $a_{i}-b_{i}=d_{i}$ for each $i$.

Another way to generalize Theorem 1.2 is if we consider the problem for
$\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}$ instead of
$\mathbb{F}_{p}\setminus\\{0\\}$. Karasev and Petrov showed that in this case,
the same statement does not hold: for example if every difference
$\mathbf{d}_{i}$ is equal to the same nonzero vector $\mathbf{d}$, then in
each vector pair, the two elements have to fall into the same
$\langle\mathbf{d}\rangle$-coset, however the nonzero cosets have an odd
number of elements in $\mathbb{F}_{p}^{n}\setminus\\{\mathbf{0}\\}$, hence
they cannot be partitioned into such pairs. However they have shown the
following result [8, Theorem 3]:

######  Theorem 1.5 (Karasev, Petrov).

Let $p$ be an odd prime and $M=\frac{p^{n}-1}{2}$. If the sets
$\\{\boldsymbol{d}_{1,1},\dots,\boldsymbol{d}_{1,n}\\}$,
$\\{\boldsymbol{d}_{2,1},\dots,\boldsymbol{d}_{2,n}\\}$, …,
$\\{\boldsymbol{d}_{M,1},\dots,\boldsymbol{d}_{M,n}\\}$ are given in
$\mathbb{F}_{p}^{n}$ such that each set is a linear basis of
$\mathbb{F}_{p}^{n}$, then there exists a function
$g:\\{1,...,M\\}\to\\{1,...,n\\}$ such that
$\mathbb{F}_{p}^{n}\setminus\\{\boldsymbol{0}\\}$ can be subdivided into
disjoint pairs $\\{\boldsymbol{a}_{i},\boldsymbol{b}_{i}\\}$ ($1\leq i\leq M$)
such that $\boldsymbol{a}_{i}-\boldsymbol{b}_{i}=\boldsymbol{d}_{i,g(i)}$ for
each $i$.

If we investigate the statement in $\mathbb{F}_{2}^{n}$ instead of
$\mathbb{F}_{p}^{n}$, and would like a perfect matching, we also need to
include the zero vector in the set of elements to be matched. Even in this
case, the claim does not hold for arbitrary nonzero difference vectors, as the
sum of the differences has to be equal to the sum of all elements of the
vector space, which is zero (see Lemma 1.10). By the main conjecture, this
would be a sufficient condition in order for an adequate perfect matching to
exist.

The authors of [1] have also verified the conjecture for the case $n\leq 5$,
and they have proved the main conjecture in the special case where among the
vectors $\mathbf{d}_{i}$, there is a value appearing at least $\frac{1}{2}m$
times, given also that all values appear an even number of times [1, Theorem
4]:

######  Theorem 1.6 (Balister, Győri, Schelp).

The main conjecture is true in the case when the vectors
$\boldsymbol{d}_{1},\boldsymbol{d}_{2},\dots,\boldsymbol{d}_{\frac{m}{2}}$ are
all equal, and for every integer $\frac{m}{4}<i\leq\frac{m}{2}$ we have
$\boldsymbol{d}_{2i-1}=\boldsymbol{d}_{2i}$.

The main idea of their proof is to first greedily select the values
$\mathbf{a}_{i}$ and $\mathbf{b}_{i}$ belonging to the differences whose value
is not equal to $\mathbf{d}_{1}$, such that if in one step we selected the
pair $(\mathbf{a}_{i},\mathbf{b}_{i})$, then in the next step we will select
the pair $(\mathbf{a}_{i}+\mathbf{d}_{1},\mathbf{b}_{i}+\mathbf{d}_{1})$ which
has the same difference. Then in the end, the remaining elements will form
pairs of difference $\mathbf{d}_{1}$.

In coding theoretical terms, Conjecture 1.1 is referred to as the Hadamard
solution version of the functional batch code conjecture. Under this
framework, Hollmann, Khathuria, Riet and Skachek [7], using a theorem of Hall
[6], proved that Conjecture 1.1 is true whenever all differences
$\mathbf{d}_{i}$ lie outside a given hyperplane $H$ of $\mathbb{F}_{2}^{n}$.
For further related work, see [14] and [15] by Yohananov and Yaakobi.

In 2023, Correia, Pokrovskiy and Sudakov [4] published the following result:

######  Theorem 1.7 (Correia, Pokrovskiy, Sudakov).

Let $G$ be a multigraph whose edges are $t$-coloured, so that each colour
class is a matching of size at least $t+20t^{15/16}$. Then there exists a
rainbow matching of size $t$ (that is, a matching with $t$ edges of all
distinct colours).

Applying this result to the graph on the vertex set $\mathbb{F}_{2}^{n}$ with
colour class $i$ consisting of the edges between pairs of difference
$\mathbf{d}_{i}$, we get that for any $M\leq 2^{n-1}-O(2^{15n/16})$ nonzero
differences $\mathbf{d}_{i}$, we can find disjoint pairs
$\\{\mathbf{a}_{i},\mathbf{b}_{i}\\}$ such that
$\mathbf{a}_{i}-\mathbf{b}_{i}=\mathbf{d}_{i}$. However this method does not
result in perfect matchings.

Gao, Ramadurai, Wanless and Wormald [5] conjectured that Theorem 1.7 holds for
$t+2$ in place of $t+20t^{15/16}$, which would resolve this problem for any
$M\leq 2^{n-1}-2$ nonzero difference vectors.

The main results of this paper are the following:

######  Theorem 1.8.

The main conjecture is true in the case when the number of distinct values
among the difference vectors is at most $n-2\log n-1$.

######  Theorem 1.9.

For every $\varepsilon>0$, there exists a value $n_{0}$ such that for all
$n\geq n_{0}$, the main conjecture is true in the case when at least a
fraction $\frac{1}{2}+\varepsilon$ of the differences are all equal.

In the context of both main results, the value that appears the most commonly
among the prescribed differences will be denoted by $\mathbf{u}$. (For Theorem
1.8, if multiple values tie for the highest number of occurrences, then pick
any one of them to be $\mathbf{u}$.)

In Section 2 we prove Theorem 1.8 by looking for so-called circuits among the
differences, meaning inclusionwise minimal, modulo $\mathbf{u}$ linearly
dependent sets. From these circuits we create multisets which we call
$\mathbf{u}$-good. Using these we can build partial matchings so that among
the remaining differences, each value will occur an even number of times. Then
the problem can be reduced to a much simpler task where there are only two
distinct difference values.

In Section 3 we prove Theorem 1.9. In order to do this, we use a result of
Bonin and Qin [2] to partition almost all of the given differences not equal
to $\mathbf{u}$ into affine subspaces, which serve as another important
building block in our construction of the perfect matching. Then we partition
the rest into $\mathbf{u}$-good multisets. We construct our matching by first
using the $\mathbf{u}$-good multisets greedily, then using the affine
subspaces which are more versatile, then completing the matching using any
pairs of identical differences, and finally with the copies of $\mathbf{u}$.

###  1.1 Notation and preliminaries

Throughout the paper, $[n]$ denotes the set $\\{1,2,\dots,n\\}$. We will also
use the notation $A\triangle B$ for the symmetric difference of two sets $A$
and $B$.

When working with sequences of elements in an abelian group $G$, the
concatenation of sequences $A$ and $B$ will be denoted by $A.B$, so if
$A=(a_{1},a_{2},...,a_{k})$ and $B=(b_{1},b_{2},...,b_{\ell})$ then
$A.B=(a_{1},...,a_{k},b_{1},...,b_{\ell})$.

We will work with multisets as well, and this concatenation operator will also
be defined for multisets (i.e., for every $c$, if element $c$ appears $m_{1}$
times in the multiset $M_{1}$ and $m_{2}$ times in the multiset $M_{2}$, then
$c$ appears $m_{1}+m_{2}$ times in the multiset $M_{1}.M_{2}$). The size of a
multiset $M$ refers to the total number of elements in $M$, counted with
multiplicities.

The notation $A\sim B$ will mean that the sequences $A$ and $B$ can be
obtained from each other by permuting their elements. If
$A=(a_{1},a_{2},...,a_{k})$ and $S=\\{i_{1},i_{2},...,i_{m}\\}\subseteq[k]$
with $i_{1}<i_{2}<...<i_{m}$, then
$A_{S}=(a_{i_{1}},a_{i_{2}},...,a_{i_{m}})$. If $A$ is a sequence or a
multiset, we let $\sum A$ denote the sum of the elements of $A$, and say that
$A$ is zero-sum if $\sum A=0$.

When a nonzero element $\mathbf{u}\in\mathbb{F}_{2}^{n}$ is fixed, we will
often work in the quotient space
$\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, which is a vector space over
$\mathbb{F}_{2}$ of dimension $n-1$, and its elements are the
$\langle\mathbf{u}\rangle$-cosets of $\mathbb{F}_{2}^{n}$. (Each
$\langle\mathbf{u}\rangle$-coset is an unordered pair of elements having a
difference of $\mathbf{u}$, and $\mathbb{F}_{2}^{n}$ can be partitioned into
$2^{n-1}$ such pairs.) Two elements of $\mathbb{F}_{2}^{n}$ are said to be
congruent mod $\boldsymbol{u}$ if they lie in the same
$\langle\mathbf{u}\rangle$-coset, i.e. they are equal or have a difference of
$\mathbf{u}$.

We will often refer to the following basic fact about $\mathbb{F}_{2}^{n}$:

######  Lemma 1.10.

The sum of the elements of the vector space $\mathbb{F}_{2}^{n}$ is
$\boldsymbol{0}$ if $n\geq 2$.

###### Proof.

For a given $1\leq i\leq n$, there are $2^{n-1}$ vectors in
$\mathbb{F}_{2}^{n}$ whose $i$-th coordinate is 0 and there are $2^{n-1}$
whose $i$-th coordinate is 1. So modulo 2, in the sum of all vectors the
$i$-th coordinate is $2^{n-1}=0$ since $n\geq 2$. ∎

##  2 Perfect matching in the case of few difference classes

In this section, we will resolve the main conjecture in a special case. Let
the nonzero differences $\mathbf{d}_{1}$, $\mathbf{d}_{2}$, …,
$\mathbf{d}_{m}$ be given in $\mathbb{F}_{2}^{n}$ such that
$\sum_{i=1}^{m}\mathbf{d}_{i}=\mathbf{0}$, where $m=2^{n-1}$. The collections
containing all differences equal to a fixed vector $\mathbf{d}$ will be called
difference classes. For a given configuration
$(\mathbf{d}_{1},\mathbf{d}_{2},\dots,\mathbf{d}_{m})$ of differences, let $t$
denote the number of nonempty difference classes. For a given value of $n$, we
would like to determine the largest integer $T(n)$ for which we can guarantee
the existence of a suitable perfect matching of $\mathbb{F}_{2}^{n}$ when
$t\leq T(n)$.

In the case $t=1$ the task is trivial, since in this case we have to divide
our vector space into $2^{n-1}$ pairs of difference $\mathbf{u}$ for some
$\mathbf{u}\neq\mathbf{0}$, so we can just take the
$\langle\mathbf{u}\rangle$-cosets of $\mathbb{F}_{2}^{n}$.

In the case $t=2$, the task can be solved using Theorem 1.6, as
$\sum\mathbf{d_{i}}=\mathbf{0}$ means that both difference classes have even
size, and at least half of the differences have to be in the same class. So we
have the structure that half of the differences are the same and the rest of
the differences can be partitioned into equal-valued pairs.

Our first main result, Theorem 1.8, states that a suitable perfect matching
exists for $t\leq n-2\log n-1$. In order to show this result, we will first
need some definitions and a technical statement about circuits and diverse
orderings of sequences in abelian groups.

###  2.1 Circuits and diverse orders

In this subsection, we will work in an arbitrary abelian group $G$.

######  Definition 2.1.

We say a sequence $A=(a_{1},a_{2},...,a_{k})$ consisting of elements in $G$ is
free of signed $t$-sums if one cannot choose indices $1\leq
i_{1}<i_{2}<...<i_{t}\leq k$ and signs
$\varepsilon_{1},...,\varepsilon_{t}\in\\{\pm 1\\}$ such that
$\sum_{j=1}^{t}\varepsilon_{j}i_{j}=0$. A sequence is free of signed $<t$-sums
if it is free of signed $t^{\prime}$-sums for all $1\leq t^{\prime}<t$.

######  Remark 2.2.

Note that in the special case $G=\mathbb{F}_{2}^{n}$, a $k$-element sequence
$A$ is free of signed $<k$-sums if and only if the ground set is a circuit in
the (linear) matroid on $[k]$ with independence defined by linear independence
of the corresponding elements of $A$ over $\mathbb{F}_{2}$. In particular, if
the group has exponent $2$ then we can take all signs $\varepsilon_{j}$ to be
$+1$, i.e. instead of signed sums we just have sums.

Only when $G=\mathbb{F}_{2}^{n}$, by an abuse of terminology we will say that
$A$ is a circuit in this case. A multiset consisting of elements in
$\mathbb{F}_{2}^{n}$ is a circuit if its elements form a circuit when listed
in any order.

######  Definition 2.3.

We say a sequence $A=(a_{1},a_{2},...,a_{k})$ consisting of elements in $G$ is
in a diverse order if the partial sums
$a_{1},a_{1}+a_{2},...,a_{1}+a_{2}+...+a_{k}$ are pairwise distinct. A
sequence or a multiset is diversely orderable if its elements can be arranged
into a diverse order.

######  Remark 2.4.

Note that a zero-sum multiset of $k$ elements in $G$ is diversely orderable if
and only if its elements can be placed in a cyclic order such that any
sequence of $k^{\prime}$ elements along the cycle (with $1\leq k^{\prime}<k$)
have a nonzero sum.

We will now prove a technical proposition about merging together two circuits
in an abelian group when certain conditions hold.

######  Proposition 2.5.

Let $G$ be an abelian group, and let $A=(a_{1},a_{2},...,a_{k})$ and
$B=(b_{1},b_{2},,...,b_{\ell})$ be zero-sum sequences of elements in $G$,
where $2\leq k\leq\ell$ are integers. Suppose that $A.B$ is free of signed
$<k$-sums and $B$ is free of signed $<\ell$-sums. Then $A.B$ is diversely
orderable, except in the following two special cases:

  * •

$k=\ell=2$, $A\sim B\sim(a,-a)$ for some $0\neq a\in G$,

  * •

$k=2$, $\ell=3$, $A\sim(a,a)$ and $B\sim(a,d,a-d)$ for some $a,d\in G$ with
$a,d\neq 0$, $2a=0$, $d\neq a$ and $a+2d\neq 0$.

The proof of this proposition will be probabilistic: we consider a uniformly
random cyclic ordering of the elements of $A.B$, and compute upper bounds on
the probabilities of each subinterval along the cycle summing to $0$. When $k$
and $\ell$ are both small, some further casework will be needed.

###### Proof.

Take a uniformly random cyclic ordering of $A.B$. For each $0\leq t\leq
k+\ell$, denote by $p_{t}$ the probability that for a uniformly random subset
$U\subseteq[k+\ell]$ of size $t$, $(A.B)_{U}$ sums to $0$. Then clearly
$p_{t}=\frac{N_{t}}{\binom{k+\ell}{t}}$, where $N_{t}$ is the number of
subsets $U$ of $[k+\ell]$ with $|U|=t$ and $\sum(A.B)_{U}=0$.

Then for each fixed subinterval of length $t$ along the cycle, the probability
that it sums to $0$ is $p_{t}$, and for a fixed $t$ there are $k+\ell$ such
subintervals.

Observe that $\sum(A.B)_{U}=0$ if and only if $\sum(A.B)_{[k+\ell]\setminus
U}=0$, since $\sum A.B=0$. Because of this, when $2\mid k+\ell$ and
$t=\frac{k+\ell}{2}$, it is sufficient to only consider $\frac{k+\ell}{2}$ of
the possible subintervals (one from each complement pair). Furthermore, since
$A.B$ is free of signed $<k$-sums, we have $p_{t}=N_{t}=0$ for each $0<t<k$,
and by the prior complementing argument, $p_{t}=N_{t}=0$ for each
$\ell<t<k+\ell$ as well.

Taking a union bound, if we can show that

$\frac{k+\ell}{2}\left(p_{k}+p_{k+1}+...+p_{\ell}\right)<1$

then this means there exists an ordering without any zero-sum subinterval.
Note that since $p_{t}=p_{k+\ell-t}$ for all $k\leq t\leq\ell$, if we convert
each term to a length between $k$ and
$\left\lfloor\frac{k+\ell}{2}\right\rfloor$, the sum contains each subinterval
length the correct number of times, including the case of $t=\frac{k+\ell}{2}$
when $2\mid k+\ell$. Let us denote
$\alpha=\frac{k+\ell}{2}\left(p_{k}+p_{k+1}+...+p_{\ell}\right)$.

Observation 1. For any $S\subseteq[k]$, there exist at most two subsets
$T\subseteq[\ell]$ such that $A_{S}.B_{T}$ is zero-sum.

Proof of observation. If $T_{1}$ and $T_{2}$ both work where $T_{2}\neq T_{1}$
and $T_{2}\neq[\ell]\setminus T_{1}$, then
$\sum(A_{S}.B_{T_{1}})-\sum(A_{S}.B_{T_{2}})=\sum B_{T_{1}\setminus
T_{2}}-\sum B_{T_{2}\setminus T_{1}}=0$, meaning that $B$ has a proper
nonempty subsequence giving a 0 sum when appropriately signed, so $B$ is not
free of signed $<\ell$-sums, contradicting the hypotheses of the Proposition.

Observation 1 means that the total number of $U\subseteq[k+\ell]$ such that
$(A.B)_{U}$ is zero-sum is at most $2^{k+1}$. We have $N_{0}=N_{k+\ell}=1$,
and so $N_{k}+N_{k+1}+...+N_{\ell}\leq 2^{k+1}-2$.

This means that

$\displaystyle\alpha$
$\displaystyle=\frac{k+\ell}{2}\left(\frac{N_{k}}{\binom{k+\ell}{k}}+\frac{N_{k+1}}{\binom{k+\ell}{k+1}}+...+\frac{N_{\ell}}{\binom{k+\ell}{\ell}}\right)$
$\displaystyle\leq\frac{k+\ell}{2}\cdot\frac{1}{\binom{k+\ell}{k}}(N_{k}+N_{k+1}+...+N_{\ell})\leq\frac{(k+\ell)(2^{k+1}-2)}{2\binom{k+\ell}{k}}=\frac{(k+\ell)(2^{k}-1)}{\binom{k+\ell}{k}}.$

Denoting $f(k,\ell)=\frac{(k+\ell)(2^{k}-1)}{\binom{k+\ell}{k}}$, if we can
show that $f(k,\ell)<1$ for a particular pair $(k,\ell)$ then we will have
proved the Proposition for that pair $(k,\ell)$. By direct computation, we
have $f(2,6)=\frac{6}{7}$, $f(3,6)=\frac{3}{4}$, $f(4,6)=\frac{5}{7}$,
$f(5,6)=\frac{31}{42}$ and $f(6,6)=\frac{9}{11}$ which are all less than 1.

Observe that
$\frac{f(k,\ell+1)}{f(k,\ell)}=\frac{k+\ell+1}{k+\ell}\cdot\frac{\binom{k+\ell}{k}}{\binom{k+\ell+1}{k}}=\frac{k+\ell+1}{k+\ell}\cdot\frac{\ell+1}{k+\ell+1}=\frac{1+\ell}{k+\ell}<1$.
So if $f(k,\ell)<1$ then $f(k,\ell^{\prime})<1$ for all $\ell^{\prime}>\ell$
too.

Further,
$\frac{f(k+1,k+1)}{f(k,k)}=\frac{2k+2}{2k}\cdot\frac{\binom{2k}{k}}{\binom{2k+2}{k+1}}\cdot\frac{2^{k+1}-1}{2^{k}-1}=\frac{k+1}{k}\cdot\frac{k+1}{4k+2}\cdot\left(2+\frac{1}{2^{k}-1}\right)$
where for $k\geq 6$, $\frac{(k+1)^{2}}{k(4k+2)}<\frac{1}{3}$ and
$2+\frac{1}{2^{k}-1}<3$, meaning that the expression is less than $1$, so by
induction, $f(k,k)<1$ for all $k\geq 6$, and combining this with the previous
observations, we are done with all cases when $\ell\geq 6$.

Therefore only the cases $(k,\ell)$ with $2\leq k\leq\ell\leq 5$ remain. The
proof for these cases can be found in the Appendix. ∎

###  2.2 $\boldsymbol{u}$-good multisets

Throughout this subsection, let $\mathbf{u}\in\mathbb{F}_{2}^{n}$ be a fixed
nonzero element. We will define $\mathbf{u}$-good multisets, which when found
among the prescribed differences, can provide a useful building block for
making a perfect matching in the case when many of the given differences are
equal to $\mathbf{u}$.

######  Definition 2.6.

A sequence $(\mathbf{d}_{1},\mathbf{d}_{2},...,\mathbf{d}_{t})$ of elements in
$\mathbb{F}_{2}^{n}$ is said to be in a mod $\boldsymbol{u}$ diverse order if
in $\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, the sequence
$(\mathbf{d}_{1}+\langle\mathbf{u}\rangle,\mathbf{d}_{2}+\langle\mathbf{u}\rangle,...,\mathbf{d}_{t}+\langle\mathbf{u}\rangle)$
is diversely ordered.

A multiset $\\{\mathbf{d}_{1},\mathbf{d}_{2},...,\mathbf{d}_{t}\\}$ of
elements in $\mathbb{F}_{2}^{n}$ is said to be a mod $\boldsymbol{u}$ circuit
if in the group $\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, the multiset
$\\{\mathbf{d}_{1}+\langle\mathbf{u}\rangle,\mathbf{d}_{2}+\langle\mathbf{u}\rangle,...,\mathbf{d}_{t}+\langle\mathbf{u}\rangle\\}$
is a circuit.

######  Definition 2.7.

A multiset $D$ of elements in $\mathbb{F}_{2}^{n}$ will be called
$\boldsymbol{u}$-good if the following conditions hold:

  * •

$\sum D=|D|\mathbf{u}$,

  * •

$D$ can be ordered in a mod $\mathbf{u}$ diverse way.

$\mathbf{u}$-good multisets have the following important placement property.

######  Proposition 2.8.

Let $D$ be a $\boldsymbol{u}$-good multiset of elements in
$\mathbb{F}_{2}^{n}$. Then in any linear subspace $U\leq\mathbb{F}_{2}^{n}$
containing $\boldsymbol{u}$ and all elements of $D$, one can find disjoint
pairs
$(\boldsymbol{a}_{1},\boldsymbol{b}_{1}),...,(\boldsymbol{a}_{t},\boldsymbol{b}_{t})$
such that $\boldsymbol{a}_{i}-\boldsymbol{b}_{i}=\boldsymbol{d}_{i}$ for all
$1\leq i\leq t$, and furthermore the union of the $t$ pairs is equal to the
union of $t$ distinct $\langle\boldsymbol{u}\rangle$-cosets of $U$.

###### Proof.

Suppose that $(\mathbf{d}_{1},...,\mathbf{d}_{t})$ is a mod $\mathbf{u}$
diverse ordering of $D$. Consider the following pairs of elements in $U$:
$(\mathbf{0},\mathbf{d}_{1}),(\mathbf{d}_{1}+\mathbf{u},\mathbf{d}_{1}+\mathbf{d}_{2}+\mathbf{u}),(\mathbf{d}_{1}+\mathbf{d}_{2},\mathbf{d}_{1}+\mathbf{d}_{2}+\mathbf{d}_{3}),...,(\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t-1}+(t-1)\mathbf{u},\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t-1}+\mathbf{d}_{t}+(t-1)\mathbf{u}=\mathbf{u})$.
These pairs have difference $\mathbf{d}_{1},\mathbf{d}_{2},...,\mathbf{d}_{t}$
respectively and are all disjoint since
$\mathbf{0},\mathbf{d}_{1},\mathbf{d}_{1}+\mathbf{d}_{2},...,\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t-1}$
are pairwise distinct mod $\mathbf{u}$. Furthermore, these pairs fully cover
$t$ distinct $\langle\mathbf{u}\rangle$-cosets in $U$. ∎

######  Remark 2.9.

Clearly Proposition 2.8 also works for an affine subspace $\mathbf{x}+U$
instead of $U$, where $U$ contains $\mathbf{u}$ and all elements of $D$: just
add $\mathbf{x}$ to every $\mathbf{a}_{i}$ and $\mathbf{b}_{i}$.

The following versatile proposition shows the usefulness of $\mathbf{u}$-good
multisets:

######  Proposition 2.10.

In $\mathbb{F}_{2}^{n}$, let $S$ be a multiset with $\sum S=|S|\boldsymbol{u}$
which does not contain any elements congruent to $\boldsymbol{0}$ mod
$\boldsymbol{u}$. Then the elements of $S$ can be partitioned into
$\boldsymbol{u}$-good multisets.

###### Proof.

We will say that a mod $\mathbf{u}$ circuit $C$ has good parity if $\sum
C=|C|\mathbf{u}$, and bad parity if $\sum C=(|C|+1)\mathbf{u}$.

Iterate the following procedure: choose the smallest available mod
$\mathbf{u}$ circuit among the elements of $S$. If there are multiple smallest
circuits, then they can be chosen in any order, except that among the
$2$-element circuits, we first choose the good-parity ones (those of the form
$(\mathbf{s},\mathbf{s})$) and then the bad-parity ones (those of the form
$(\mathbf{s},\mathbf{s}+\mathbf{u})$).

In this way, all elements of $S$ have been partitioned into mod $\mathbf{u}$
circuits, since $\sum S\equiv 0\pmod{\mathbf{u}}$ and each circuit also has
$\mathbf{0}$ sum mod $\mathbf{u}$, so the remaining elements always have
$\mathbf{0}$ sum mod $\mathbf{u}$, so are linearly dependent mod $\mathbf{u}$,
so a mod $\mathbf{u}$ circuit can always be chosen as long as there are still
some elements remaining.

Furthermore, since $\sum S=|S|\mathbf{u}$, we have $\sum\limits_{C}(\sum
C-|C|\mathbf{u})=\mathbf{0}$ (where $C$ iterates through the circuits in the
obtained partitioning), so the total number of bad-parity circuits in the
partitioning is even (as good-parity circuits contribute $\mathbf{0}$ to the
sum and bad-parity circuits contribute $\mathbf{u}$).

Now construct the classes of the partitioning in the following way: let each
good circuit form its own class, and out of the bad circuits, form pairs in an
arbitrary way, and every such pair of circuits is combined to form a class.

We now show that every such class is $\mathbf{u}$-good indeed: the first
condition is satisfied, as good-parity circuits have $\sum C=|C|\mathbf{u}$,
and if $C_{1}$ and $C_{2}$ are bad-parity circuits, then
$\sum(C_{1}.C_{2})=\sum C_{1}+\sum
C_{2}=(|C_{1}|+1)\mathbf{u}+(|C_{2}|+1)\mathbf{u}=|C_{1}.C_{2}|\mathbf{u}$.

For a good-parity circuit
$C=(\mathbf{c}_{1},\mathbf{c}_{2},...,\mathbf{c}_{t})$, every ordering is mod
$\mathbf{u}$ diverse: supposing we had
$\mathbf{c}_{1}+...+\mathbf{c}_{\ell}\equiv\mathbf{c}_{1}+...+\mathbf{c}_{\ell^{\prime}}\pmod{\mathbf{u}}$
for $0\leq\ell<\ell^{\prime}\leq t-1$, then this would mean
$\mathbf{c}_{\ell+1}+\mathbf{c}_{\ell+2}+...+\mathbf{c}_{\ell^{\prime}}\equiv\mathbf{0}\pmod{\mathbf{u}}$,
meaning that $C$ has a linearly dependent proper subset, contradicting the
fact that it is a circuit.

For a pair of bad-parity circuits $A=(\mathbf{a}_{1},...,\mathbf{a}_{k})$ and
$B=(\mathbf{b}_{1},...,\mathbf{b}_{\ell})$, where $A$ was chosen earlier than
$B$ without loss of generality, let
$\overline{A}=(\overline{\mathbf{a}_{1}},...,\overline{\mathbf{a}_{k}})$ and
$\overline{B}=(\overline{\mathbf{b}_{1}},...,\overline{\mathbf{b}_{\ell}})$
denote the sequences where each element is replaced by its
$\langle\mathbf{u}\rangle$-coset. Now in the group
$\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, apply Proposition 2.5 to
$\overline{A}$ and $\overline{B}$, whose conditions are satisfied:

  * •

they are zero-sum sequences with $2\leq k\leq\ell$,

  * •

$\overline{A}.\overline{B}$ is free of $<k$-sums, as otherwise $A$ would not
have been the smallest mod $\mathbf{u}$ circuit at the time it was chosen,

  * •

$\overline{B}$ is free of $<\ell$-sums, as otherwise $B$ would not be a mod
$\mathbf{u}$ circuit.

Also note that the two exceptional cases in this Proposition cannot occur, as
both of them involve three equal elements in $\overline{A}.\overline{B}$ (in
the first exceptional case we would have $a=-a$ since
$\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$ has exponent $2$), however any
pairs of equal elements in $S$ have been removed at the beginning of the
procedure (as a 2-element good-parity circuit), so the union of all bad
circuits, and hence $\overline{A}.\overline{B}$, can only contain at most two
copies of the same element mod $\mathbf{u}$.

This means that by the Proposition, $\overline{A}.\overline{B}$ can be
diversely ordered, so $A.B$ can be diversely ordered mod $\mathbf{u}$. ∎

######  Remark 2.11.

As in $\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, the largest independent
set over $\mathbb{F}_{2}$ has size $n-1$, each mod $\mathbf{u}$ circuit has
size $\leq n$. So the proof of Proposition 2.10 obtains a partitioning where
each $\mathbf{u}$-good multiset has size $\leq 2n$.

###  2.3 Proof of Theorem 1.8

We are now ready to prove our first main result:

Theorem 1.8. The main conjecture is true in the case when the number of
distinct values among the difference vectors is at most $n-2\log n-1$.

###### Proof.

Let the distinct values of the given differences be $\mathbf{u_{1}}$,
$\mathbf{u_{2}}$, $\dots$, $\mathbf{u_{t}}$, where $t\leq n-2\log n-1$, and
for each $1\leq i\leq t$, $\mathbf{u_{i}}$ appears $n_{i}$ times with
$n_{1}\geq n_{2}\geq\dots\geq n_{t}$. Here we have $\sum_{i=1}^{t}n_{i}=m$. In
particular, $n_{1}\geq\frac{m}{t}$.

In $\mathbb{F}_{2}^{n}$, a vector space over $\mathbb{F}_{2}$, let
$U=\langle\mathbf{u_{1}},\dots,\mathbf{u_{t}}\rangle$ and let $k=\dim U$.
(Then $k\leq t$.) We can assume that $k\geq 2$, as otherwise $t=1$, and this
is a case that we have already seen. Call the $U$-cosets of
$\mathbb{F}_{2}^{n}$ layers. Then in the perfect matching that we will make,
each vector pair has to be within a layer. We will create perfect matchings of
each layer separately, and we will not modify any finished layers later.
Altogether there are $2^{n-k}$ layers.

Our algorithm will consist of 3 phases:

  * •

Phase 1: We will create perfect matchings in some (less than $t$) layers in
such a way that an even number of vectors will remain in each difference
class.

  * •

Phase 2: We will create perfect matchings in some (less than $t$) layers in
such a way that in each difference class, the number of remaining vectors will
be divisible by $2^{k-1}$.

  * •

Phase 3: All of the remaining differences will be used to create homogeneous
layers (i.e. layers consisting of differences from only one class).

Now we explain the details of each phase.

Phase 1. Let $H=\\{\mathbf{u_{i}}:2\leq i\leq t,n_{i}\equiv 1\pmod{2}\\}$, and
we will use the notation $\mathbf{u}=\mathbf{u_{1}}$.

Using Proposition 2.10, we partition $H$ into $\mathbf{u}$-good multisets.
This is possible, since
$0=\sum_{i=1}^{t}n_{i}\mathbf{u}_{i}=n_{1}\mathbf{u}+\sum H$, and the number
of elements in $H$ has the same parity as the total number of all differences
not equal to $\mathbf{u}$, which in turn has the same parity as the total
number of differences equal to $\mathbf{u}_{1}$, and hence
$|H|\mathbf{u}=n_{1}\mathbf{u}=\sum H$.

Take the $\mathbf{u}$-good multisets in turn, and for each multiset $D$, make
a perfectly matched layer in the following way: use Proposition 2.8 for an
unused layer $\mathbf{x}+U$. It can be used since $U$ contains $\mathbf{u}$
and all elements of $D$. So we get $|D|$ disjoint pairs in $\mathbf{x}+U$
using the differences in $D$, whose union is equal to a union of
$\langle\mathbf{u}\rangle$-cosets, therefore the matching of the layer can be
completed using differences of value $\mathbf{u}$.

After this phase, the number of remaining differences is even in the classes
of $\mathbf{u}_{2},...,\mathbf{u}_{t}$, and this is true for $\mathbf{u}$ as
well, as each remaining layer requires an even number of differences in total.

Phase 2. Perform the following step for each $2\leq i\leq t$ in turn.

If the number of remaining copies of $\mathbf{u_{i}}$ has a remainder of
$m_{i}$ modulo $2^{k-1}$ (where $2\leq m_{i}\leq 2^{k-1}-2$ is even), then let
us make a perfect matching of a new layer using $m_{i}$ copies of
$\mathbf{u_{i}}$ and $2^{k-1}-m_{i}$ copies of $\mathbf{u}$. This can be done,
as this is the problem in the main conjecture for $\mathbb{F}_{2}^{k}$
(actually for a translate of it, but this does not matter), and as $m_{i}$ and
$2^{k-1}-m_{i}$ are even, the sum of the difference vectors we need to use is
0, and we have already resolved the conjecture in the case of two difference
classes.

(If $m_{i}=0$ then we do not need to do anything with the $i$-th class.)

Phase 3. As the number of remaining vectors in each class is divisible by
$2^{k-1}$, and for any $\mathbf{0}\neq\mathbf{d}\in U$ we can partition $U$
(or any translate of it) into $2^{k-1}$ pairs of difference $\mathbf{d}$, this
phase can be trivially performed, completing the perfect matching of
$\mathbb{F}_{2}^{n}$ in the required manner.

Observe that all three phases can always be performed: in phase 1, in every
layer we use at least 3 elements of $H$, so we make at most $\frac{t-1}{3}$
completed layers. And in phase 2, we make less than $t$ layers. So in the
first two phases, altogether we used $\leq\frac{4}{3}(t-1)\cdot 2^{k-1}$
copies of $\mathbf{u}$. And indeed we did have this many copies of
$\mathbf{u}$ at our disposal, as

$\frac{4}{3}t(t-1)\cdot 2^{k-1}\leq\frac{4}{3}t(t-1)\cdot
2^{t-1}\leq\frac{4}{3}t(t-1)\cdot 2^{n-2\log
n-2}=\frac{1}{3}t(t-1)\frac{2^{n}}{n^{2}}<\frac{1}{3}\cdot 2^{n}<2^{n-1}$

and so $\frac{4}{3}(t-1)\cdot 2^{k-1}<\frac{2^{n-1}}{t}=\frac{m}{t}\leq
n_{1}$. ∎

##  3 Perfect matching in the case of many equal vectors

In this chapter, we resolve the main conjecture (for sufficiently large $n$)
in the special case when at least a fraction $\frac{1}{2}+\varepsilon$ of the
difference vectors are all equal, and the others are arbitrary. So in contrast
to the theorem of Balister, Győri and Schelp (see Theorem 1.6), here we do not
require that all differences appear an even number of times.

###  3.1 Affine flats

In order to create a perfect matching of $\mathbb{F}_{2}^{n}$ according to the
given differences in the main conjecture, it is worthwhile to group the given
differences into classes with nice additive combinatorial properties. An
example of such a class would be a $k$-dimensional affine subspace of
$\mathbb{F}_{2}^{n}$ (also called a $k$-flat).

For a fixed $k\geq 1$, we are interested in the minimal integer $s$ (as a
function of $n$) such that any subset $S\subseteq\mathbb{F}_{2}^{n}$ of size
$s$ is guaranteed to contain a $k$-flat.

In the case $k=2$, a set $S\subseteq\mathbb{F}_{2}^{n}$ contains a $2$-flat if
and only if it is not a Sidon set. (A subset $S$ of an abelian group $G$ is
called a Sidon set if the only solutions to $a+b=c+d$ with $a,b,c,d\in G$ are
the trivial solutions where $(c,d)$ is a permutation of $(a,b)$.) Bose and
Ray-Chaudhuri [3] have shown that for $k=2$, the smallest such $s$ is
$\Theta(2^{n/2})$.

It turns out that even for larger (fixed) values of $k$, the smallest size $s$
required is still exponentially small compared to $2^{n}$. Going along the
lines of Szemerédi’s Cube Lemma (see [13, Corollary 2.1]), a result of Bonin
and Qin [2, Lemma 21] states the following:

######  Proposition 3.1.

Given integers $n\geq k\geq 2$, and any $s\geq 2\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}$, any subset
$S\subseteq\mathbb{F}_{2}^{n}$ with $|S|\geq s$ contains a $k$-flat.

This will mean that for $n$ sufficiently large compared to $k$, and a given
difference set $D$ with $|D|\gg 2^{n\left(1-\frac{1}{2^{k-1}}\right)}$, almost
all elements of $D$ may be partitioned into $k$-flats.

Note that an easy corollary of Lemma 1.10 is that for any $k\geq 2$, the sum
of the elements of any $k$-flat in $\mathbb{F}_{2}^{n}$ is $\mathbf{0}$. We
will use this fact later.

###  3.2 Blocking ratios

In order for us to flexibly find partial matchings among a certain set of
elements in $\mathbb{F}_{2}^{n}$ according to given sequences of differences,
we define the following notions:

######  Definition 3.2.

Given a multiset $D=\\{\mathbf{d}_{1},\mathbf{d}_{2},...,\mathbf{d}_{k}\\}$ of
differences in $\mathbb{F}_{2}^{n}$, define a subset
$S\subseteq\mathbb{F}_{2}^{n}$ to be blocking for $D$ if in
$\mathbb{F}_{2}^{n}\setminus S$ there do not exist $k$ pairwise disjoint pairs
$(\mathbf{a}_{1},\mathbf{b}_{1}),(\mathbf{a}_{2},\mathbf{b}_{2}),...,(\mathbf{a}_{k},\mathbf{b}_{k})$
of elements such that $\mathbf{a}_{i}-\mathbf{b}_{i}=\mathbf{d}_{i}$ for all
$1\leq i\leq k$.

Let the blocking ratio of $D$ be defined as

$\beta(D)=\frac{\min\\{|S|:~{}S\subseteq\mathbb{F}_{2}^{n},~{}S\textrm{ is
blocking for }D\\}}{2^{n}}.$

For example, for any nonzero $\mathbf{d}\in\mathbb{F}_{2}^{n}$,
$\\{\mathbf{d}\\}$ has a blocking ratio of $\frac{1}{2}$, since a set
$S\subseteq\mathbb{F}_{2}^{n}$ is blocking for $\\{\mathbf{d}\\}$ if and only
if it contains at least one element of each $\langle\mathbf{d}\rangle$-coset.

Since in our algorithm, we will pack differences while respecting cosets of
$\langle\mathbf{u}\rangle$, where $\mathbf{u}$ is the most commonly appearing
difference, it is worthwhile to also define the following analogous version of
the blocking ratio:

######  Definition 3.3.

Let $\mathbf{u}\in\mathbb{F}_{2}^{n}\setminus\\{\mathbf{0}\\}$ be fixed.
Define a subset $S\subseteq\mathbb{F}_{2}^{n}$ to be $\boldsymbol{u}$-blocking
for $D$ if $S$ is a union of some $\langle\mathbf{u}\rangle$-cosets and in
$\mathbb{F}_{2}^{n}\setminus S$ there do not exist $k$ pairwise disjoint pairs
$(\mathbf{a}_{1},\mathbf{b}_{1}),(\mathbf{a}_{2},\mathbf{b}_{2}),...,(\mathbf{a}_{k},\mathbf{b}_{k})$
of elements such that the following two conditions hold:

  * •

$\mathbf{a}_{i}-\mathbf{b}_{i}=\mathbf{d}_{i}$ for all $1\leq i\leq k$,

  * •

and
$\\{\mathbf{a}_{1},...,\mathbf{a}_{k},\mathbf{b}_{1},...,\mathbf{b}_{k}\\}$ is
equal to a union of some $\langle\mathbf{u}\rangle$-cosets.

Let the $\boldsymbol{u}$-blocking ratio of $D$ be defined as

$\beta_{\mathbf{u}}(D)=\frac{\min\\{|S|:~{}S\subseteq\mathbb{F}_{2}^{n},~{}S\textrm{
is }\mathbf{u}\textrm{-blocking for }D\\}}{2^{n}}.$

As an example, $\beta_{\mathbf{u}}(\\{\mathbf{u}\\})=1$, and for any
$\mathbf{0}\neq\mathbf{d}\neq\mathbf{u}$,
$\beta_{\mathbf{u}}(\\{\mathbf{d},\mathbf{d}\\})=\frac{1}{2}$, since in
$\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, the cosets can be paired to
each other based on congruence modulo $\mathbf{d}$, and a set (consisting of
full $\langle\mathbf{u}\rangle$-cosets) is $\mathbf{u}$-blocking for
$\\{\mathbf{d},\mathbf{d}\\}$ if and only if at least one
$\langle\mathbf{u}\rangle$-coset is chosen from each such pair. If assigning
disjoint pairs to the differences in $D$ is impossible in such a way that the
pairs together only cover full $\langle\mathbf{u}\rangle$-cosets (such as in
the case $D=\\{\mathbf{d}\\}$ for $\mathbf{0}\neq\mathbf{d}\neq\mathbf{u}$),
then $S=\emptyset$ will be $\mathbf{u}$-blocking for $D$, so
$\beta_{\mathbf{u}}(D)=0$.

The following proposition will be used for constructing a perfect matching of
$\mathbb{F}_{2}^{n}$ according to a list of given differences grouped into
classes that have large enough $\mathbf{u}$-blocking ratios:

######  Proposition 3.4.

In the main conjecture, suppose that the multiset of given differences
$(\boldsymbol{d}_{1},\boldsymbol{d}_{2},...,\boldsymbol{d}_{m})$ is
partitioned into several classes $D_{1},D_{2},...,D_{\ell}$ such that for some
fixed value of
$\boldsymbol{u}\in\mathbb{F}_{2}^{n}\setminus\\{\boldsymbol{0}\\}$, the
following holds for all $1\leq i\leq\ell$:

$\beta_{\mathbf{u}}(D_{i})>\frac{\sum\limits_{j=1}^{i-1}|D_{j}|}{2^{n-1}}$

.

Then there is an appropriate perfect matching of $\mathbb{F}_{2}^{n}$
corresponding to the given differences.

###### Proof.

We construct a perfect matching by iteratively going through each class
$D_{i}$ in increasing order of $i$. For each $D_{i}$, we assign to the
differences in $D_{i}$ disjoint pairs of elements of $\mathbb{F}_{2}^{n}$ that
have not yet been used for previous classes $D_{j}$ ($j<i$). Our procedure
will respect $\langle\mathbf{u}\rangle$-cosets, meaning that for each $i$, the
elements of $\mathbb{F}_{2}^{n}$ assigned to the differences in $D_{i}$ will
form a union of $\langle\mathbf{u}\rangle$-cosets.

For each $D_{i}$, the number of elements of $\mathbb{F}_{2}^{n}$ already used
for previous classes is $2\sum_{j=1}^{i-1}|D_{j}|$, and since

$\beta_{\mathbf{u}}(D_{i})>\frac{2\sum\limits_{j=1}^{i-1}|D_{j}|}{2^{n}},$

the already-used elements are not $\mathbf{u}$-blocking for $D_{i}$, hence it
is possible to assign pairs of new elements to $D_{i}$ in a way that respects
$\langle\mathbf{u}\rangle$-cosets. ∎

###  3.3 Blocking ratio of $\boldsymbol{u}$-good multisets

In this subsection and the following one, the image of a vector
$\mathbf{v}\in\mathbb{F}_{2}^{n}$ under the quotient map
$q:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$ will be
denoted by $\overline{\mathbf{v}}$. When given a subset $S$ of
$\mathbb{F}_{2}^{n}$ which is a union of $\langle\mathbf{u}\rangle$-cosets,
define $\overline{S}=q(S)\subseteq\mathbb{F}_{2}^{n}$. Note that this
correspondence can be used in both directions, since $S$ can be recovered from
$\overline{S}$ by taking $S=q^{-1}(\overline{S})$.

We have seen that $\mathbf{u}$-good multisets (as per Definition 2.7) have a
positive $\mathbf{u}$-blocking ratio: this is equivalent to the statement of
Proposition 2.8. Using the following lemma, we can place a better lower bound
on $\beta_{\mathbf{u}}(D)$ for any $\mathbf{u}$-good multiset $D$.

######  Lemma 3.5.

Let $G$ be a finite abelian group, and let $X\subseteq G$. Subsets of $G$ of
the form $\\{g+x:x\in X\\}$ (where $g\in G$ is arbitrary) will be called
translates of $X$. Then in $G$, we can select at least
$\frac{|G|}{|X|(|X|-1)+1}$ pairwise disjoint translates of $X$.

###### Proof.

Keep choosing translates of $X$ greedily which are disjoint from the
previously chosen ones. Let the chosen translates be $g_{1}+X$, $g_{2}+X$, …,
$g_{\ell}+X$, and suppose that no further translate of $X$ can be chosen that
is disjoint from these.

Then for every $g_{\ell+1}\in G$, $g_{\ell+1}+X$ intersects at least one of
the earlier translates, so there exist $x,x^{\prime}\in X$ and $1\leq
i\leq\ell$ such that $g_{\ell+1}+x=g_{i}+x^{\prime}$, so
$g_{\ell+1}=g_{i}+x^{\prime}-x$. But an upper bound on the number of elements
expressible in this form is $\ell(1+|X|(|X|-1))$ (as $x^{\prime}-x$ can take
at most $|X|(|X|-1)$ nonzero values), so $|G|\leq\ell(1+|X|(|X|-1))$, proving
the lemma. ∎

######  Remark 3.6.

If the group $G$ has exponent 2 (that is, for every $g\in G$ we have $g+g=0$),
then $x^{\prime}-x$ can take at most $\binom{|X|}{2}$ nonzero values, hence in
this case, the lemma can be improved to say that at least
$\frac{|G|}{\binom{|X|}{2}+1}$ pairwise disjoint translates of $X$ can be
selected.

######  Proposition 3.7.

Let $D=\\{\boldsymbol{d}_{1},\boldsymbol{d}_{2},...,\boldsymbol{d}_{t}\\}$ be
a $\boldsymbol{u}$-good multiset for some nonzero
$\boldsymbol{u}\in\mathbb{F}_{2}^{n}$. Then
$\beta_{\boldsymbol{u}}(D)\geq\frac{1}{\binom{t}{2}+1}$.

###### Proof.

Suppose on the contrary that $S\subseteq\mathbb{F}_{2}^{n}$ is
$\mathbf{u}$-blocking for $D$ with $|S|<\frac{2^{n}}{\binom{t}{2}+1}$.
Assuming $(\overline{\mathbf{d}_{1}},...,\overline{\mathbf{d}_{t}})$ is
diversely ordered in $\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$, the
partial sums $\mathbf{d}_{1}$, $\mathbf{d}_{1}+\mathbf{d}_{2}$, …,
$\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t}$ are pairwise distinct
modulo $\mathbf{u}$. Consider the following set
$\overline{X}\subseteq\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$:
$\overline{X}=\\{\overline{\mathbf{d}_{1}},\overline{\mathbf{d}_{1}}+\overline{\mathbf{d}_{2}},...,\overline{\mathbf{d}_{1}}+\overline{\mathbf{d}_{2}}+...+\overline{\mathbf{d}_{t}}=\overline{\mathbf{0}}\\}$
(where we have used the fact that
$\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t}=t\mathbf{u}\equiv\mathbf{0}\pmod{\mathbf{u}}$).

Now
$|\overline{S}|<\frac{|\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle|}{\binom{t}{2}+1}$.
Now by Remark 3.6, we can select at least
$\frac{|\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle|}{\binom{t}{2}+1}$
pairwise disjoint translates of $\overline{X}$ in
$\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$. At least one of these
translates must be disjoint from $\overline{S}$; let us choose such a
translate $\overline{Y}$, which is equal to
$\\{\overline{\mathbf{y}\vphantom{d}},\overline{\mathbf{y}\vphantom{d}}+\overline{\mathbf{d}_{1}},...,\overline{\mathbf{y}\vphantom{d}}+\overline{\mathbf{d}_{1}}+...+\overline{\mathbf{d}_{t-1}}\\}$
for some $\mathbf{y}\in\mathbb{F}_{2}^{n}$. Then $Y$ is disjoint from $S$, is
a union of $\langle\mathbf{u}\rangle$-cosets, and can be subdivided into the
$t$ pairs $(\mathbf{y},\mathbf{y}+\mathbf{d}_{1})$,
$(\mathbf{y}+\mathbf{d}_{1}+\mathbf{u},\mathbf{y}+\mathbf{d}_{1}+\mathbf{d}_{2}+\mathbf{u})$,
$(\mathbf{y}+\mathbf{d}_{1}+\mathbf{d}_{2},\mathbf{y}+\mathbf{d}_{1}+\mathbf{d}_{2}+\mathbf{d}_{3})$,
…,
$(\mathbf{y}+\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t-1}+(t-1)\mathbf{u},\mathbf{y}+\mathbf{d}_{1}+\mathbf{d}_{2}+...+\mathbf{d}_{t-1}+\mathbf{d}_{t}+(t-1)\mathbf{u}=\mathbf{y}+\mathbf{u})$
with differences $\mathbf{d}_{1}$, $\mathbf{d}_{2}$, …, $\mathbf{d}_{t}$
respectively. So $S$ is not actually $\mathbf{u}$-blocking for $D$, which is a
contradiction. ∎

###  3.4 Blocking ratio of $k$-flats

######  Definition 3.8.

A $k$-flat $F\subseteq\mathbb{F}_{2}^{n}$ will be called $\boldsymbol{u}$-nice
if no element of $F$ is congruent to $\mathbf{0}$ mod $\mathbf{u}$ and no two
elements of $F$ are congruent to each other mod $\mathbf{u}$.

Observe that any $2$-flat $F\subseteq\mathbb{F}_{2}^{n}$ can be written in the
form
$F=\\{\mathbf{x},\mathbf{x}+\mathbf{a}_{1},\mathbf{x}+\mathbf{a}_{2},\mathbf{x}+\mathbf{a}_{1}+\mathbf{a}_{2}\\}$
for some $\mathbf{x},\mathbf{a}_{1},\mathbf{a}_{2}\in\mathbb{F}_{2}^{n}$ and
$\mathbf{a}_{1}\neq\mathbf{a}_{2}$,
$\mathbf{a}_{1},\mathbf{a}_{2}\neq\mathbf{0}$. It is easy to check that if $F$
is $\mathbf{u}$-nice, then
$\\{\mathbf{x},\mathbf{x}+\mathbf{a}_{1},\mathbf{x}+\mathbf{a}_{2},\mathbf{x}+\mathbf{a}_{1}+\mathbf{a}_{2}\\}$
is a $\mathbf{u}$-good multiset and hence by Proposition 3.7,
$\beta_{\mathbf{u}}(F)\geq\frac{1}{7}$. Let us improve this result:

######  Proposition 3.9.

For a $\mathbf{u}$-nice $2$-flat $F\subseteq\mathbb{F}_{2}^{n}$, we have
$\beta_{\mathbf{u}}(F)\geq\frac{3}{8}$.

###### Proof.

Write $F=\mathbf{x}+L$ for $L=\langle\mathbf{a}_{1},\mathbf{a}_{2}\rangle$.
Since $F$ is $\mathbf{u}$-nice, the elements
$\mathbf{x},\mathbf{a}_{1},\mathbf{a}_{2}$ are linearly independent mod
$\mathbf{u}$. (Otherwise one could find an element of $F$ congruent to
$\mathbf{0}$ or two elements of $F$ congruent to each other mod $\mathbf{u}$.)
So let $C=\langle\mathbf{u},\mathbf{x},\mathbf{a}_{1},\mathbf{a}_{2}\rangle$
which is a $4$-dimensional subspace of $\mathbb{F}_{2}^{n}$. Also by the
$\mathbf{u}$-nice condition, the following three orderings of $F$ are all
diverse mod $\mathbf{u}$:

  * •

$F_{1}=(\mathbf{x}+\mathbf{a}_{1},\mathbf{x}+\mathbf{a}_{2},\mathbf{x}+\mathbf{a}_{1}+\mathbf{a}_{2},\mathbf{x})$,

  * •

$F_{2}=(\mathbf{x}+\mathbf{a}_{1},\mathbf{x}+\mathbf{a}_{1}+\mathbf{a}_{2},\mathbf{x}+\mathbf{a}_{2},\mathbf{x})$,

  * •

$F_{3}=(\mathbf{x}+\mathbf{a}_{2},\mathbf{x}+\mathbf{a}_{1},\mathbf{x}+\mathbf{a}_{1}+\mathbf{a}_{2},\mathbf{x})$.

Let $V=\mathbb{F}_{2}^{n}$, and then
$\overline{V}=\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$. In $\overline{V}$,
take the linear subspace
$\overline{C}=\langle\overline{\mathbf{x}},\overline{\mathbf{a}_{1}},\overline{\mathbf{a}_{2}}\rangle$
and consider each $\overline{C}$-coset of $\overline{V}$. Suppose that $S$ is
$\mathbf{u}$-blocking for $F$, and there exists a $\overline{C}$-coset
$\overline{\mathbf{y}}+\overline{C}$ of $\overline{V}$ such that at most two
of the eight $\langle\mathbf{u}\rangle$-cosets in
$\overline{\mathbf{y}}+\overline{C}$ are contained in $\overline{S}$.

According to the basic construction in Proposition 2.8, if $S$ is
$\mathbf{u}$-blocking for a $\mathbf{u}$-good multiset diversely ordered as
$D=(\mathbf{d}_{1},\mathbf{d}_{2},...,\mathbf{d}_{t})$ then for every
$\mathbf{x}\in\mathbb{F}_{2}^{n}$, $S$ must contain at least one
$\langle\mathbf{u}\rangle$-coset out of the partial sums
$\overline{\mathbf{x}\vphantom{d}},\overline{\mathbf{x}\vphantom{d}}+\overline{\mathbf{d}_{1}},\overline{\mathbf{x}\vphantom{d}}+\overline{\mathbf{d}_{1}}+\overline{\mathbf{d}_{2}},...,\overline{\mathbf{x}\vphantom{d}}+\overline{\mathbf{d}_{1}}+\overline{\mathbf{d}_{2}}+...+\overline{\mathbf{d}_{t-1}}$.

Applying this to $F_{1}$, $F_{2}$ and $F_{3}$, this means that for each
$\overline{\mathbf{z}}\in\overline{\mathbf{y}}+\overline{C}$, $\overline{S}$
contains at least one element from each
$\overline{\mathbf{z}}+\overline{R_{j}}$ ($j=1,2,3$) for the following sets
$\overline{R_{j}}$:

  * •

$\overline{R_{1}}=\\{\overline{\mathbf{0}},\overline{\mathbf{x}\vphantom{0}}+\overline{\mathbf{a}_{1}\vphantom{0}},\overline{\mathbf{a}_{1}\vphantom{0}}+\overline{\mathbf{a}_{2}\vphantom{0}},\overline{\mathbf{x}\vphantom{0}}\\}$,

  * •

$\overline{R_{2}}=\\{\overline{\mathbf{0}},\overline{\mathbf{x}\vphantom{0}}+\overline{\mathbf{a}_{1}\vphantom{0}},\overline{\mathbf{a}_{2}\vphantom{0}},\overline{\mathbf{x}\vphantom{0}}\\}$,

  * •

$\overline{R_{3}}=\\{\overline{\mathbf{0}},\overline{\mathbf{x}\vphantom{0}}+\overline{\mathbf{a}_{2}\vphantom{0}},\overline{\mathbf{a}_{1}\vphantom{0}}+\overline{\mathbf{a}_{2}\vphantom{0}},\overline{\mathbf{x}\vphantom{0}}\\}$.

Without loss of generality, assume $\overline{\mathbf{y}}\in\overline{S}$.
Then depending on whether $\overline{\mathbf{y}}+\overline{C}$ has another
element in $\overline{S}$, and what that element is, we can always find
$\overline{\mathbf{z}}\in\overline{\mathbf{y}}+\overline{C}$ and $j=1,2,3$
with none of the elements of $\overline{\mathbf{z}}+\overline{R_{j}}$
contained in $\overline{S}$, causing a contradiction. For each case, the table
below lists one such possible choice of
$\overline{\mathbf{z}}+\overline{R_{j}}$:

Elements of $(\overline{\mathbf{y}}+\overline{C})\cap\overline{S}$ |  $\overline{\mathbf{z}}+\overline{R_{j}}$ with contradiction
---|---
$\overline{\mathbf{y}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{a}_{1}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{a}_{2}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{a}_{1}}+\overline{\mathbf{a}_{2}}+\overline{R_{2}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{a}_{1}}+\overline{\mathbf{a}_{2}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{x}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{1}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{1}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{2}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{1}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$
$\overline{\mathbf{y}},\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{1}}+\overline{\mathbf{a}_{2}}$ | $\overline{\mathbf{y}}+\overline{\mathbf{x}}+\overline{\mathbf{a}_{2}}+\overline{R_{1}}$

This means that in every $\overline{C}$-coset of $\overline{V}$, at least 3 of
the 8 elements are contained in $\overline{S}$. Therefore,
$\frac{|S|}{2^{n}}\geq\frac{3}{8}$. ∎

######  Remark 3.10.

In this proof, if $\overline{S}$ contains three
$\langle\mathbf{u}\rangle$-cosets of $\overline{\mathbf{y}}+\overline{C}$ then
a case-by-case check reveals that we can always find
$\overline{\mathbf{z}}+\overline{R_{j}}$ disjoint from $\overline{S}$ (where
$\overline{\mathbf{z}}\in\overline{\mathbf{y}}+\overline{C}$), except in the
case when the three $\langle\mathbf{u}\rangle$-cosets are in the same
$\langle\overline{\mathbf{a}_{1}},\overline{\mathbf{a}_{2}}\rangle$-coset.

######  Proposition 3.11.

Let $k,n\geq 2$. For a $\boldsymbol{u}$-nice $k$-flat
$F\subseteq\mathbb{F}_{2}^{n}$, we have

$\beta_{\boldsymbol{u}}(F)\geq\frac{1}{2}-\frac{1}{2^{k+1}}-\frac{1}{2^{n-k(2^{k}+2)}}.$

Note that Proposition 3.9 already proves the case $k=2$.

###### Proof.

Letting $\mathbf{x}$ be an arbitrary element of $F$, we can write
$F=\mathbf{x}+L$ where
$L=\langle\mathbf{a}_{1},\mathbf{a}_{2},...,\mathbf{a}_{k}\rangle$ with
$\mathbf{a}_{1},...,\mathbf{a}_{k}\in\mathbb{F}_{2}^{n}$ linearly independent.
Again we use the notation $V=\mathbb{F}_{2}^{n}$, and then
$\overline{V}=\mathbb{F}_{2}^{n}/\langle\mathbf{u}\rangle$. Since $F$ is
$\mathbf{u}$-nice, the elements $\mathbf{x},\mathbf{a}_{1},...,\mathbf{a}_{k}$
are linearly independent mod $\mathbf{u}$, so let us define
$C=\langle\mathbf{u},\mathbf{x},\mathbf{a}_{1},...,\mathbf{a}_{k}\rangle=\langle\mathbf{u},\mathbf{x}\rangle\oplus
L$ which is a $k+2$-dimensional subspace of $V$, and correspondingly
$\overline{C}=\langle\overline{\mathbf{x}},\overline{\mathbf{a}_{1}},...,\overline{\mathbf{a}_{k}}\rangle$,
a $k+1$-dimensional subspace of $\overline{V}$ satisfying
$\overline{C}=\langle\overline{\mathbf{x}}\rangle\oplus\overline{L}$.

Given $H\subseteq V$ which is a union of $\langle\mathbf{u}\rangle$-cosets,
and a $\mathbf{u}$-nice $2$-flat $E$, let us say that $\overline{H}$
accommodates $E$ if there exists $\overline{\mathbf{z}}\in\overline{V}$ and an
ordering $(\mathbf{e}_{1},\mathbf{e}_{2},\mathbf{e}_{3},\mathbf{e}_{4})$ of
$E$ such that
$\\{\overline{\mathbf{z}},\overline{\mathbf{z}}+\overline{\mathbf{e}_{1}},\overline{\mathbf{z}}+\overline{\mathbf{e}_{1}}+\overline{\mathbf{e}_{2}},\overline{\mathbf{z}}+\overline{\mathbf{e}_{1}}+\overline{\mathbf{e}_{2}}+\overline{\mathbf{e}_{3}}\\}\subseteq\overline{H}$.
If this is true, then (by the idea of Proposition 2.8, as $E$ is
$\mathbf{u}$-good with all orderings diverse mod $\mathbf{u}$) we can select
four pairwise disjoint pairs of elements in $H$ with differences
$\mathbf{e}_{1},\mathbf{e}_{2},\mathbf{e}_{3},\mathbf{e}_{4}$, such that their
union is a union of $\langle\mathbf{u}\rangle$-cosets.

Consider the $\overline{C}$-cosets of $\overline{V}$. We would like to
partition $F$ into $2$-flats $E_{1},E_{2},...,E_{2^{k-2}}$ and find distinct
$\overline{C}$-cosets $\overline{\mathbf{y}_{i}}+\overline{C}$ ($1\leq i\leq
2^{k-2}$) in $\overline{V}$ such that for every $i$,
$(\overline{\mathbf{y}_{i}}+\overline{C})\setminus\overline{S}$ accommodates
$E_{i}$. If this can be done, then $S$ is not $\mathbf{u}$-blocking for $F$,
as we can combine the element pairs obtained for each $E_{i}$ to get $2^{k}$
pairwise disjoint pairs in $\mathbb{F}_{2}^{n}\setminus S$ such that each
element $\mathbf{f}$ of $F$ has one pair with difference $\mathbf{f}$, and the
pairs altogether form a union of $\langle\mathbf{u}\rangle$-cosets.

We start with the following auxiliary claim:

Claim 1. Let $k\geq 2$ and $F\subseteq\mathbb{F}_{2}^{n}$ be a
$\mathbf{u}$-nice $k$-flat. Define $L$ and $C$ as above. Then if
$\overline{H}\subseteq\overline{C}$ is a subset having at least 2 elements in
one of the two $\overline{L}$-cosets of $\overline{C}$ and at least $2^{k}-1$
elements in the other $\overline{L}$-coset, then $F$ can be partitioned into
2-flats, all of which are accommodated by $\overline{H}$.

Proof of Claim 1. The property of whether $\overline{H}$ accommodates a given
2-flat is invariant under translations of $\overline{H}$, so we can assume
that
$\\{\mathbf{0},\overline{\mathbf{v}}\\}\subseteq\overline{H}\cap\overline{L}$
and
$(\overline{\mathbf{x}}+\overline{L})\setminus\\{\overline{\mathbf{x}}+\overline{\mathbf{w}}\\}\subseteq\overline{H}$
with $\mathbf{v},\mathbf{w}\in L$, $\mathbf{v}\neq\mathbf{0},\mathbf{u}$. Now
partition $F$ into $2^{k-1}$ pairs of sum $\mathbf{v}$, and arbitrarily pair
up these pairs to form $2^{k-2}$ quadruples. Each quadruple is a $2$-flat of
the form
$\\{\mathbf{x}+\mathbf{t}_{1},\mathbf{x}+\mathbf{t}_{1}+\mathbf{v},\mathbf{x}+\mathbf{t}_{2},\mathbf{x}+\mathbf{t}_{2}+\mathbf{v}\\}$
for $\mathbf{t}_{1},\mathbf{t}_{2}\in L$ incongruent mod $\mathbf{v}$. Any
such quadruple is accommodated by $\overline{H}$, as one can take the ordering
$(\mathbf{x}+\mathbf{t}_{1},~{}\mathbf{x}+\mathbf{t}_{1}+\mathbf{v},~{}\mathbf{x}+\mathbf{t}_{2}+\mathbf{v},~{}\mathbf{x}+\mathbf{t}_{2})$,
whose corresponding partial sums in $\overline{C}$ are
$(\overline{\mathbf{0}},\overline{\mathbf{x}\vphantom{0}}+\overline{\mathbf{t}_{1}\vphantom{0}},\overline{\mathbf{v}\vphantom{0}},\overline{\mathbf{x}\vphantom{0}}+\overline{\mathbf{t}_{2}\vphantom{0}})$.
If $\overline{\mathbf{w}}=\overline{\mathbf{t}_{1}}$ then swap the first two
differences in the ordering, and if
$\overline{\mathbf{w}}=\overline{\mathbf{t}_{2}}$, then swap the last two
differences, hence getting a good ordering that avoids the partial sum
$\overline{\mathbf{x}}+\overline{\mathbf{w}}$. ∎

Let us prove the following claim by induction on $k$:

Claim 2. Let $k\geq 2$ and $F\subseteq\mathbb{F}_{2}^{n}$ be a
$\mathbf{u}$-nice $k$-flat. Define $L$ and $C$ as above. Then if
$\overline{H}\subseteq\overline{C}$ is a subset of size at least $2^{k}+2$,
then $F$ can be partitioned into $2$-flats, all of which are accommodated by
$\overline{H}$. Furthermore if $|\overline{H}|=2^{k}+1$ and there is no such
partitioning, then one of the two $\overline{L}$-cosets of $\overline{C}$ is
fully contained in $\overline{H}$ and the other intersects $\overline{H}$ in
just one element.

Proof of Claim 2. Firstly note that in the case $k=2$, $F$ is a $2$-flat
itself which is accommodated by $\overline{H}$ if and only if $C\setminus H$
is not $\mathbf{u}$-blocking for $F$. So the two parts of our statement follow
from Proposition 3.9 and Remark 3.10 respectively.

Now let $k\geq 3$, and suppose that $F$ has no good partitioning. For each
$1\leq i\leq k$, define
$L_{i}=\langle\mathbf{a}_{1},...,\mathbf{a}_{i-1},\mathbf{a}_{i+1},...,\mathbf{a}_{k}\rangle$.
If there exists $i$ such that both $\mathbf{x}+L_{i}$ and
$\mathbf{x}+\mathbf{a}_{i}+L_{i}$ can be partitioned into $2$-flats
accommodated by $\overline{H}$, then $F$ can also be partitioned in this way.
So suppose that for all $i$, it is impossible to partition either
$\mathbf{x}+L_{i}$ or $\mathbf{x}+\mathbf{a}_{i}+L_{i}$ in this way. Without
loss of generality, we may assume that for every $i$, $\mathbf{x}+L_{i}$
cannot be partitioned like this. For each $i$, clearly $\mathbf{x}+L_{i}$ is a
$\mathbf{u}$-nice $(k-1)$-flat, for which the Claim can be recursively used.
Let $C_{i}=\langle\mathbf{x},\mathbf{u}\rangle\oplus L_{i}$,
$\overline{H_{i}}=\overline{H}\cap\overline{C_{i}}$ and
$\overline{H^{\prime}_{i}}=\overline{H}\setminus\overline{C_{i}}=\overline{H}\cap(\overline{\mathbf{a}_{i}}+\overline{C_{i}})$,
Then by the inductive hypothesis, if $|\overline{H_{i}}|\geq 2^{k-1}+2$ then
$\mathbf{x}+L_{i}$ can be partitioned into $2$-flats accommodated by
$\overline{H_{i}}$ and hence by $\overline{H}$. Similarly, if
$|\overline{H^{\prime}_{i}}|\geq 2^{k-1}+2$ then $\mathbf{x}+L_{i}$ can again
be partitioned into $2$-flats accommodated by $\overline{H^{\prime}_{i}}$
(which we can work in instead of $\overline{H_{i}}$, as translation of a set
does not affect whether it accommodates a certain $2$-flat) and hence by
$\overline{H}$. So we must have $|\overline{H_{i}}|\leq 2^{k-1}+1$ and
$|\overline{H^{\prime}_{i}}|\leq 2^{k-1}+1$ for every $i$. Overall, if $F$ has
no good partitioning then $\overline{H}\subseteq\overline{C}$ is of size $\leq
2^{k}+2$.

If $|\overline{H}|=2^{k}+2$ then for each $i$,
$|\overline{H_{i}}|=|\overline{H^{\prime}_{i}}|=2^{k-1}+1$, and as neither
$\overline{H_{i}}$ nor $\overline{H^{\prime}_{i}}$ can accommodate
$\mathbf{x}+L_{i}$, by the induction hypothesis one of the two
$\overline{L_{i}}$-cosets of $\overline{C_{i}}$ must be fully contained in
$\overline{H}$ (say $\overline{\mathbf{y}_{i}}+\overline{L_{i}}$), and
similarly one of the two $\overline{L_{i}}$-cosets of
$\overline{\mathbf{a}_{i}}+\overline{C_{i}}$ must also be fully contained in
$\overline{H}$ (say $\overline{\mathbf{y}^{\prime}_{i}}+\overline{L_{i}}$).
The other two $\overline{L_{i}}$-cosets of $\overline{C}$ (namely
$\overline{\mathbf{y}_{i}}+\overline{\mathbf{a}_{i}}+\overline{L_{i}}$ and
$\overline{\mathbf{y}^{\prime}_{i}}+\overline{\mathbf{a}_{i}}+\overline{L_{i}}$)
must contain only one element of $\overline{H}$ each.

Now we show that $\overline{\mathbf{y}_{1}}$ and
$\overline{\mathbf{y}^{\prime}_{1}}$ lie in the same $\overline{L}$-coset of
$\overline{C}$. Supposing otherwise, $\overline{C_{2}}$ intersects all four
$\overline{L_{1}}$-cosets of $\overline{C}$ in $2^{k-2}$ elements, which means
that $\overline{\mathbf{y}_{1}}+\overline{L_{1}}$ and
$\overline{\mathbf{y}^{\prime}_{1}}+\overline{L_{1}}$ (both contained in $H$),
which together intersect all four $\overline{L_{2}}$-cosets of $\overline{C}$,
contain at least $2^{k-2}$ elements in each $\overline{L_{2}}$-coset, so there
cannot be any $\overline{L_{2}}$-cosets containing only one element of
$\overline{H}$, a contradiction.

Without loss of generality,
$\overline{\mathbf{y}_{1}},\overline{\mathbf{y}^{\prime}_{1}}\in\overline{L}$,
so $\overline{L}\subseteq\overline{H}$. Then $\overline{x}+\overline{L}$ has 2
elements of $\overline{H}$ so by Claim 1, the partitioning is possible, a
contradiction.

If $|\overline{H}|=2^{k}+1$ then for each $i$, one of $|\overline{H_{i}}|$ and
$|\overline{H^{\prime}_{i}}|$ is $2^{k-1}+1$ and the other is $2^{k-1}$.
Without loss of generality, $|\overline{H_{i}}|=2^{k-1}+1$ for all $i$; then
by the inductive hypothesis, one of the $\overline{L}$-cosets contains
$2^{k-1}$ elements of $\overline{H_{i}}$ and the other contains just one. We
can assume that $\overline{L}$ has $2^{k-1}$ elements of $\overline{H_{1}}$;
then it automatically contains all $2^{k-2}$ elements of
$\overline{H_{i}}\cap\overline{H_{1}}$ for all $2\leq i\leq k$, so actually
$\overline{L}$ must contain $2^{k-1}$ elements of $\overline{H_{i}}$ for all
$i$. But then $\overline{L}\cap\overline{C_{i}}\subseteq\overline{H}$ for each
$i$, meaning that $\overline{H}$ has at least $2^{k}-1$ elements in
$\overline{L}$. If it has only $2^{k}-1$ then the partitioning is possible by
Claim 1, and if it has $2^{k}$ then we have the exceptional case stated in the
Claim. ∎

Clearly Claim 2 can also be used for translates of $\overline{C}$ instead of
$\overline{C}$. So let us use it for the $\overline{C}$-cosets of
$\overline{V}$. If a $\overline{C}$-coset $\overline{\mathbf{y}}+\overline{C}$
satisfies $|(\overline{\mathbf{y}}+\overline{C})\cap\overline{S}|\leq
2^{k}-2$, then by Claim 2, $F$ can be partitioned into $2$-flats all
accommodated by $(\overline{\mathbf{y}}+\overline{C})\setminus\overline{S}$.
Let $N_{k}$ be the number of ways to partition a $k$-flat into $2$-flats. As a
partitioning can be encoded by giving an ordering of the vectors,
$N_{k}\leq(2^{k})!\leq 2^{k\cdot 2^{k}}$. If we have $2^{k-2}$ cosets for
which $F$ is partitioned in the same way, then we can take this partitioning
of $F$ and accordingly place one $2$-flat into each coset. So if the number of
cosets which intersect $\overline{S}$ in at most $2^{k}-2$ elements is at
least $N_{k}\cdot 2^{k-2}$, then this holds by the pigeonhole principle, and
$S$ is not $\mathbf{u}$-blocking for $F$. The total number of
$\overline{C}$-cosets of $\overline{V}$ is $2^{n-k-2}$, so if $S$ is
$\mathbf{u}$-blocking,

$|\overline{S}|\geq(2^{n-k-2}-N_{k}\cdot 2^{k-2})(2^{k}-1),$

and

$|S|\geq(2^{n-k-1}-N_{k}\cdot 2^{k-1})(2^{k}-1)\geq
2^{n-1}-2^{n-k-1}-2^{k\cdot(2^{k}+2)},$

meaning that

$\beta_{\mathbf{u}}(F)\geq\frac{1}{2}-\frac{1}{2^{k+1}}-\frac{1}{2^{n-k(2^{k}+2)}}.$

∎

###  3.5 Perfect matching in the case of many equal vectors

We are now ready to prove Theorem 1.9.

Theorem 1.9. For every $\varepsilon>0$, there exists a value $n_{0}$ such that
for all $n\geq n_{0}$, the main conjecture is true in the case when at least a
fraction $\frac{1}{2}+\varepsilon$ of the differences are all equal.

###### Proof.

Let $\mathbf{u}\in\mathbb{F}_{2}^{n}$ denote the value that appears most
frequently among the given differences
$\mathbf{d_{1}},\mathbf{d_{2}},\dots,\mathbf{d_{m}}$. (Here the number of
differences is $m=\frac{1}{2}\cdot 2^{n}$.)

Let $H$ denote the multiset of vectors $\mathbf{d_{i}}$ which are not equal to
$\mathbf{u}$. Then $|H|<\left(\frac{1}{2}-\varepsilon\right)m$.

For constructing an appropriate perfect matching of $\mathbb{F}_{2}^{n}$, we
will group the given differences into several classes $D_{1}$, $D_{2}$, …,
$D_{\ell}$ in such a way that Proposition 3.4 can be used.

First we will define the grouping, then give the order of the groups, and at
the end of the proof we will explain why the condition of the Proposition is
satisfied when the classes are ordered in this way.

First of all, each difference equal to $\mathbf{u}$ will form its own class,
and $\beta_{\mathbf{u}}(\\{\mathbf{u}\\})=1$.

For differences not equal to $\mathbf{u}$, first we check if there is a pair
of equal differences $\mathbf{d}\neq\mathbf{u}$. As long as there is such a
pair, the pair will form its own class, and
$\beta_{\mathbf{u}}(\\{\mathbf{d},\mathbf{d}\\})=\frac{1}{2}$.

Let $H^{\prime}$ consist of the remaining elements of $H$. Then the elements
of $H^{\prime}$ are all distinct and are not congruent to $\mathbf{0}$ mod
$\mathbf{u}$. Furthermore, $\sum H^{\prime}=|H^{\prime}|\mathbf{u}$.

Now divide the elements of $H^{\prime}$ into two classes $H^{\prime}_{1}$ and
$H^{\prime}_{2}$ such that none of the two classes contains a pair of elements
which are congruent mod $\mathbf{u}$. This can be done in the following way,
for example: consider all $\langle\mathbf{u}\rangle$-cosets which have two
elements in $H^{\prime}$, and for each such coset, place one element in
$H^{\prime}_{1}$ and the other in $H^{\prime}_{2}$. For those
$\langle\mathbf{u}\rangle$-cosets which have only one element in $H^{\prime}$,
place those elements into $H^{\prime}_{1}$.

Let $k=\left\lfloor\frac{1}{3}\log_{2}n\right\rfloor$. In $H^{\prime}_{1}$,
repeatedly find a $k$-flat and put its elements into a new class, removing
them from $H^{\prime}_{1}$. (Each $k$-flat forms its own distinct class of
$2^{k}$ differences.) Do this until no more $k$-flats can be found among the
remaining elements of $H^{\prime}_{1}$. Then do the same for $H^{\prime}_{2}$.
By Proposition 3.11, each class $D_{i}$ so obtained satisfies
$\beta_{\mathbf{u}}(D_{i})\geq\frac{1}{2}-\frac{1}{2^{k+1}}-\frac{1}{2^{n-k(2^{k}+2)}}$.

Now by Proposition 3.1, the number of remaining elements in $H^{\prime}_{1}$
will be less than $2\cdot~{}2^{n\left(1-\frac{1}{2^{k-1}}\right)}$, and the
same is true for $H^{\prime}_{2}$. Let $H^{\prime\prime}$ consist of all
remaining elements from $H^{\prime}_{1}$ and $H^{\prime}_{2}$; then
$|H^{\prime\prime}|<4\cdot 2^{n\left(1-\frac{1}{2^{k-1}}\right)}$.

Note that every $k$-flat has an even number of elements and $\mathbf{0}$ sum,
so $|H^{\prime\prime}|\equiv|H^{\prime}|\pmod{2}$ and $\sum
H^{\prime\prime}=\sum H^{\prime}$, meaning that $\sum
H^{\prime\prime}=|H^{\prime\prime}|\mathbf{u}$ holds. $H^{\prime\prime}$ does
not contain any element congruent to $\mathbf{0}$ mod $\mathbf{u}$.

By Proposition 2.10, $H^{\prime\prime}$ can be partitioned into
$\mathbf{u}$-good multisets. (Here they are actually sets, since the elements
of $H^{\prime\prime}$ are all distinct.) By Remark 2.11, every such multiset
has size $\leq 2n$. Each $\mathbf{u}$-good multiset will form its own class.
By Proposition 3.7, every such class $D$ will have
$\beta_{\mathbf{u}}(D)\geq\frac{1}{\binom{2n}{2}+1}\geq\frac{1}{2n^{2}}$.

Now order the classes in the following way: first put the $\mathbf{u}$-good
multisets from $H^{\prime\prime}$, then the $k$-flats from
$H^{\prime}\setminus H^{\prime\prime}$, then the pairs
$\\{\mathbf{d},\mathbf{d}\\}$ and finally the singleton classes
$\\{\mathbf{u}\\}$. Then the condition of Proposition 3.4 will be satisfied:

  * •

For a $\mathbf{u}$-good class $D_{i}$, we have
$\sum_{j=1}^{i-1}|D_{j}|<|H^{\prime\prime}|<4\cdot
2^{n\left(1-\frac{1}{2^{k-1}}\right)}$. So

$\frac{\sum_{j=1}^{i-1}|D_{j}|}{2^{n-1}}<8\cdot
2^{-\frac{1}{2^{k-1}}n}<\frac{1}{2n^{2}}\leq\beta_{\mathbf{u}}(D_{i}),$

since

$16n^{2}<2^{\frac{1}{2^{k-1}}n}~{}\Leftrightarrow~{}2\log_{2}n+4<\frac{1}{2^{k-1}}n~{}\Leftrightarrow~{}2^{k-1}<\frac{n}{2\log_{2}n+4}$

,

which is true because $2^{k-1}\leq
2^{\frac{1}{3}\log_{2}n-1}=\frac{1}{2}n^{1/3}\leq\frac{n}{2\log_{2}n+4}$ for
$n$ large enough.

  * •

For a $k$-flat of $H^{\prime}\setminus H^{\prime\prime}$, we have
$\sum_{j=1}^{i-1}|D_{j}|<|H^{\prime}|<(\frac{1}{2}-\varepsilon)\cdot 2^{n-1}$,
so $\frac{\sum_{j=1}^{i-1}|D_{j}|}{2^{n-1}}<\frac{1}{2}-\varepsilon$, and
using the fact that $k+1\geq\frac{1}{3}\log_{2}n$,

$\beta_{\mathbf{u}}(D_{i})\geq\frac{1}{2}-\frac{1}{2^{k+1}}-\frac{1}{2^{n-k(2^{k}+2)}}\geq\frac{1}{2}-\frac{1}{n^{1/3}}-\frac{1}{2^{n-\frac{1}{3}\log_{2}n(n^{1/3}+2)}}>\frac{1}{2}-\varepsilon$

for $n$ large enough.

  * •

For a pair $\\{\mathbf{d},\mathbf{d}\\}$, we have
$\sum_{j=1}^{i-1}|D_{j}|<|H|<(\frac{1}{2}-\varepsilon)\cdot 2^{n-1}$, so

$\beta_{\mathbf{u}}(D_{i})=\frac{1}{2}>\frac{1}{2}-\varepsilon>\frac{\sum_{j=1}^{i-1}|D_{j}|}{2^{n-1}}.$

  * •

For singletons $\\{\mathbf{u}\\}$, we have $\sum_{j=1}^{i-1}|D_{j}|<2^{n-1}$,
so $\beta_{\mathbf{u}}(D_{i})=1>\frac{\sum_{j=1}^{i-1}|D_{j}|}{2^{n-1}}$.

So an appropriate perfect matching of $\mathbb{F}_{2}^{n}$ exists according to
the given differences. ∎

## Acknowledgements

I am very grateful to Zoltán Lóránt Nagy for his helpful comments and advice
regarding my research and this paper itself.

I would like to thank Péter Csikvári for bringing the conjecture of Balister,
Győri and Schelp to my attention, and for his helpful comments and advice
regarding my research.

I would also like to thank Ago-Erik Riet for calling my attention to the
coding-theoretical literature on batch codes related to the main conjecture.

## References

  * [1] Balister, P. N., Győri, E., & Schelp, R. H. (2011). Coloring vertices and edges of a graph by nonempty subsets of a set. European Journal of Combinatorics, 32(4), 533-537.
  * [2] Bonin, J. E., & Qin, H. (2000). Size functions of subgeometry-closed classes of representable combinatorial geometries. Discrete Mathematics, 224(1-3), 37-60.
  * [3] Bose, R. C., & Ray-Chaudhuri, D. K. (1960). On a class of error correcting binary group codes. Information and control, 3(1), 68-79.
  * [4] Correia, D. M., Pokrovskiy, A., & Sudakov, B. (2023). Short Proofs of Rainbow Matchings Results. International Mathematics Research Notices, 2023(14), 12441-12476.
  * [5] Gao, P., Ramadurai, R., Wanless, I. M., & Wormald, N. (2021). Full rainbow matchings in graphs and hypergraphs. Combinatorics, Probability and Computing, 1-19.
  * [6] Hall, M. (1952). A combinatorial problem on abelian groups. Proceedings of the American Mathematical Society, 3(4), 584-587.
  * [7] Hollmann, H. D., Khathuria, K., Riet, A. E., & Skachek, V. (2023). On some batch code properties of the simplex code. Designs, Codes and Cryptography, 91(5), 1595-1605.
  * [8] Karasev, R. N., & Petrov, F. V. (2012). Partitions of nonzero elements of a finite field into pairs. Israel Journal of Mathematics, 192(1), 143-156.
  * [9] Kohen, D., & Sadofschi, I. (2010). A new approach on the seating couples problem. arXiv preprint arXiv:1006.2571.
  * [10] Kohen, D., & Sadofschi, I. (2016). On a generalization of the seating couples problem. Discrete Mathematics, 339(12), 3017-3019.
  * [11] Meszka, M., Pasotti, A., & Pellegrini, M. A. (2023). The seating couple problem in even case. arXiv preprint arXiv:2308.16553.
  * [12] Preissmann, E., & Mischler, M. (2009). Seating Couples Around the King’s Table and a New Characterization of Prime Numbers. The American Mathematical Monthly, 116(3), 268-272.
  * [13] Setyawan, Y. (1998). Combinatorial Number Theory: Results of Hilbert, Schur, Folkman, and Hindman. Simon Fraser University.
  * [14] Yohananov, L., & Yaakobi, E. (2021). Almost optimal construction of functional batch codes using Hadamard codes. 2021 IEEE International Symposium on Information Theory (ISIT), 3139-3144.
  * [15] Yohananov, L., & Yaakobi, E. (2022). Almost optimal construction of functional batch codes using extended Simplex codes. IEEE Transactions on Information Theory, 68(10), 6434-6451.

## Appendix

Here we finish the remaining cases of the following Proposition.

Proposition 2.5. Let $G$ be an abelian group, and let
$A=(a_{1},a_{2},...,a_{k})$ and $B=(b_{1},b_{2},,...,b_{\ell})$ be zero-sum
sequences of elements in $G$, where $2\leq k\leq\ell$ are integers. Suppose
that $A.B$ is free of signed $<k$-sums and $B$ is free of signed $<\ell$-sums.
Then $A.B$ is diversely orderable, except in the following two special cases:

  * •

$k=\ell=2$, $A\sim B\sim(a,-a)$ for some $0\neq a\in G$,

  * •

$k=2$, $\ell=3$, $A\sim(a,a)$ and $B\sim(a,d,a-d)$ for some $a,d\in G$ with
$a,d\neq 0$, $2a=0$, $d\neq a$ and $a+2d\neq 0$.

###### Proof of Proposition 2.5: cases of small $k$ and $\ell$.

In the remaining cases we have $2\leq k\leq\ell\leq 5$. For these cases, the
following observation will help: for any distinct
$U,U^{\prime}\subseteq[k+\ell]$, if $\sum(A.B)_{U}=\sum(A.B)_{U^{\prime}}=0$
then $|U\triangle U^{\prime}|\geq k$. (Otherwise, the indices corresponding to
$U\triangle U^{\prime}$ would give a $<k$-element signed sum of zero.)

Therefore the characteristic vectors of subsets $U\subseteq[k+\ell]$
corresponding to zero sums form a binary code of length $k+\ell$ and minimum
distance at least $k$. By the Hamming bound, the size $N$ of such a code
satisfies

$N\leq\frac{2^{k+\ell}}{\sum\limits_{i=0}^{t}\binom{k+\ell}{i}}$ $None$

where $t=\left\lfloor\frac{k-1}{2}\right\rfloor$. Here $N$ is the number of
subsets $U$ of $[k+\ell]$ with $\sum U=0$, so
$N=N_{0}+N_{1}+...+N_{k+\ell}=2+N_{k}+N_{k+1}+...+N_{\ell}$.

Case $k=\ell=5$: In this case, by $(*)$,
$N=2+N_{5}\leq\frac{2^{10}}{\binom{10}{0}+\binom{10}{1}+\binom{10}{2}}<19$. So
$N_{5}\leq 16$, and
$\alpha=5\cdot\frac{N_{5}}{\binom{10}{5}}\leq\frac{20}{63}<1$.

Case $k=4$, $\ell=5$: Let us consider $N_{4}$. For every $S\subseteq[4]$,
there are at most two subsets $T\subseteq[5]$ with $A_{S}.B_{T}=0$, and if
there are two then they are complements of each other, and hence they have
different sizes. So there is at most one $T$ such that $\sum A_{S}.B_{T}$ is
zero-sum and $|S|+|T|=4$. For every $U,U^{\prime}\subseteq[9]$ with
$\sum(A.B)_{U}=\sum(A.B)_{U^{\prime}}=0$, either $U=U^{\prime}$ or
$|U\triangle U^{\prime}|\geq 4$. So supposing that $|U|=|U^{\prime}|=4$ with
$U\neq U^{\prime}$, this means that $|U\cap U^{\prime}|\neq 3$, and as
complements of zero-sum sequences are also zero-sum,
$|U\triangle\overline{U^{\prime}}|\geq 4$ holds too, meaning that $|U\cap
U^{\prime}|\not\in\\{0,1\\}$ either, so $|U\cap U^{\prime}|=2$. Take
$U^{\prime}=\\{1,2,3,4\\}$. Now either $U=\\{1,2,3,4\\}$ or $U$ has an
intersection with $\\{1,2,3,4\\}$ of size $2$, which can be extended to a
zero-sum set of size $4$ in at most one way, meaning that $N_{4}\leq 7$
altogether. This means
$\alpha=\frac{9}{2}\cdot\frac{2N_{4}}{\binom{9}{4}}\leq\frac{1}{2}<1$.

Case $k=\ell=4$: For each $S\subseteq[4]$ there are at most two
$T\subseteq[4]$ with $\sum A_{S}.B_{T}=0$, and similarly to the previous case,
one can obtain that any $U,U^{\prime}\subseteq[8]$ of size $4$ and zero sum
cannot have an intersection of size 3. $\\{1,2,3,4\\}$ and $\\{5,6,7,8\\}$ are
zero-sum, so by investigating the intersection sizes of $U$ with these two
sets, this means that any other zero-sum $U$ has exactly two elements from
$\\{1,2,3,4\\}$, and any two such elements can be extended to a zero-sum set
of size $4$ in at most two ways, giving $N_{4}\leq 2+\binom{4}{2}\cdot 2=14$.
So $\alpha=4\cdot\frac{N_{4}}{\binom{8}{4}}\leq\frac{4}{5}<1$.

Case $k=3$, $\ell=5$: For each $S\subseteq[3]$ there are at most two
$T\subseteq[5]$ with $\sum A_{S}.B_{T}=0$ (and if there are two then they are
complements of each other), and any zero-sum $U,U^{\prime}\subseteq[8]$ are
equal or have Hamming distance at least 3. So if $|U|=|U^{\prime}|=3$ then
$|U\cap U^{\prime}|=2$ is impossible, and by taking the complement of
$U^{\prime}$, $|U\cap U^{\prime}|=0$ is also impossible. If $|U|=3$ and
$|U^{\prime}|=4$ then $|U\cap U^{\prime}|=3$ is impossible, and by taking the
complement of $U^{\prime}$, $|U\cap U^{\prime}|=0$ is also impossible. Fixing
$U=\\{1,2,3\\}$, this means that $3$-element zero-sum index sets have
intersection $1$ or $3$ with $U$, and every such intersection can only occur
once (meaning that $N_{3}\leq 4$), and $4$-element zero-sum index sets have
intersection $1$ or $2$ with $U$, and every such intersection can only occur
once (meaning that $N_{4}\leq\binom{3}{1}+\binom{3}{2}=6$). Therefore
$\alpha=4\left(\frac{2N_{3}}{\binom{8}{3}}+\frac{N_{4}}{\binom{8}{4}}\right)\leq
4\left(\frac{1}{7}+\frac{3}{35}\right)=\frac{32}{35}<1$.

Case $k=3$, $\ell=4$: Using the techniques seen above, one obtains that for
any zero-sum $U\subseteq[7]$ of size $3$, either $U=\\{1,2,3\\}$ or
$|U\cap\\{1,2,3\\}|=1$, and one-element subsets of $\\{1,2,3\\}$ can be
extended to zero-sum sets in $[7]$ of size $3$ in at most two ways. This gives
altogether $N_{3}\leq 7$, however we need $N_{3}\leq 4$ to show that
$\alpha=\frac{7}{2}\cdot\frac{2N_{3}}{\binom{7}{3}}=\frac{N_{3}}{5}<1$. So
supposing $N_{3}\geq 5$, there is a 1-element subset of $\\{1,2,3\\}$ that can
be extended in two ways. We can assume that this is $\\{1\\}$. As three-
element zero-sum subsets cannot intersect in exactly 2 elements (or else they
would violate the minimum distance of $\geq 3$), one can assume that
$\\{1,4,5\\}$ and $\\{1,6,7\\}$ correspond to zero-sum subsets, meaning that
$a_{1}+b_{1}+b_{2}=a_{1}+b_{3}+b_{4}=0$. Still avoiding intersections of size
2, without loss of generality, we can also assume that $\\{2,4,6\\}$ is a
further zero-sum subset, so $a_{2}+b_{1}+b_{3}=0$ too. But then
$(a_{1},a_{2},b_{3},a_{3},b_{1},b_{2},b_{4})$ can be seen to be a good cyclic
ordering, as each subinterval of length 3 has an intersection of size $2$ with
a known zero-sum subset of size $3$ ($\\{a_{1},a_{2},a_{3}\\}$,
$\\{a_{1},b_{1},b_{2}\\}$, $\\{a_{1},b_{3},b_{4}\\}$ or
$\\{a_{2},b_{1},b_{3}\\}$), and hence does not itself have zero sum.

Case $k=\ell=3$: Here $\\{1,2,3\\}$ and $\\{4,5,6\\}$ are zero-sum, and two
zero-sum triples cannot have an intersection of size 2, meaning that there
cannot be any further zero-sum triples in $[6]$, and $N_{3}\leq 2$, meaning
that $\alpha=3\cdot\frac{N_{3}}{\binom{6}{3}}\leq\frac{3}{10}<1$.

Case $k=2$, $\ell=5$: Let $A=(a,-a)$. We need
$\alpha=\frac{7}{2}\left(\frac{2N_{2}}{\binom{7}{2}}+\frac{2N_{3}}{\binom{7}{3}}\right)<1\Leftrightarrow
5N_{2}+3N_{3}<15$. By Observation 1,
$N_{2}+N_{3}+N_{4}+N_{5}=2(N_{2}+N_{3})\leq 6$, so $N_{2}+N_{3}\leq 3$. Hence
$5N_{2}+3N_{3}\leq 5(N_{2}+N_{3})\leq 15$ with equality if and only if
$N_{2}=3$ and $N_{3}=0$. But $B$ is free of signed $<5$-sums, so at most one
of its elements can belong to the set $\\{a,-a\\}$, and there is no zero-sum
pair within $B$. This implies that the number of zero-sum pairs is at most
$2$, so $N_{2}=3$ cannot happen, unless $2a=0$. However in this case $A=(a,a)$
and $B=(a,d,e,f,g)$, and $(a,d,a,e,a,f,g)$ is a good cyclic ordering (as using
$2a=0$, every two- or three-element subinterval along this cycle sums to a sum
of $1$, $2$ or $3$ distinct elements of $B$ which must be nonzero).

Case $k=2$, $\ell=4$: Let $A=(a,-a)$ and $B=(c,d,e,f)$. We need
$\alpha=3\left(\frac{2N_{2}}{\binom{6}{2}}+\frac{N_{3}}{\binom{6}{3}}\right)<1\Leftrightarrow
8N_{2}+3N_{3}<20$. By Observation 1, $N_{2}+N_{3}+N_{4}=2N_{2}+N_{3}\leq 6$.
If $N_{2}=0$ then $N_{3}\leq 6$ so $3N_{3}<20$. Again, as $B$ has no signed
$<4$-sums, at most one of its elements can belong to $\\{a,-a\\}$, and there
is no zero-sum pair within $B$. Distinguish three cases depending on the value
of $N_{2}$.

If $N_{2}=1$ then $\\{a,-a\\}$ is the only zero sum of size 2. Both $\\{a\\}$
and $\\{-a\\}$ might be extended to a 3-element zero-sum multiset in at most
two ways, giving $N_{3}\leq 4$. If $8N_{2}+3N_{3}<20$ we are done, so we can
assume $N_{3}=4$. Then $\\{a\\}$ and $\\{-a\\}$ extend to 3-element zero-sum
multisets in two ways each. If $\\{a,c,d\\}$ has zero sum then for example
$\\{a,c,e\\}$ cannot have zero sum, as then we would have $d=e$. A complement
of a zero-sum set is also zero-sum, so the only case is that the 3-element
zero-sums are $a+c+d=a+e+f=(-a)+c+d=(-a)+e+f=0$, meaning that $a=-a$ so
$2a=0$. In this case, $(a,e,d,a,f,c)$ is a good cyclic ordering of the six
elements: it doesn’t have 2- or 3-element zero-sum subintervals, as we have
enumerated all of those and they do not appear.

If $N_{2}=2$ then $A=(a,-a)$, $B=(a,d,e,f)$ where $a\neq-a$ (so $2a\neq 0$).
For $N_{3}\leq 1$ we are then done, and for $N_{3}\geq 2$, $\\{a\\}$ in $A$
must extend to three-element zero-sum multisets in two ways, and $N_{3}=2$. So
we can assume $a+a+f=a+d+e=0$, meaning that $B=(a,d,a-d,-2a)$. Since $B$ is
free of signed $<4$-sums, we have $a,d,2a,3a\neq 0$, $a\neq 2d$ and $d\neq\pm
a,\pm 2a,\pm 3a$. Then $(-a,a-d,a,d,a,-2a)$ is a good cyclic ordering, which
is easy to check.

If $N_{2}=3$ then we must have $a=-a$ (i.e., $2a=0$), and $A=(a,a)$ and
$B=(a,d,e,f)$, and then $(a,d,a,e,a,f)$ is a good cyclic ordering, similarly
to the case seen for $(k,\ell)=(2,5)$.

Case $k=2$, $\ell=3$: Let $A=(a,-a)$ and $B=(c,d,e)$. If $N_{2}\leq 1$ then
$\alpha=\frac{5}{2}\cdot\frac{2N_{2}}{\binom{5}{2}}\leq\frac{1}{2}<1$, so
$N_{2}\geq 2$. Similarly to the previous cases, at most one element in $B$ can
be $\pm a$, giving $N_{2}=2$ if $a\neq-a$ and $N_{2}=3$ if $a=-a$. In the
former case, $A=(a,-a)$ and $B=(a,d,-a-d)$ where the ordering
$(-a,-a-d,a,a,d)$ works. In the latter case, we have $A=(a,a)$ and
$B=(a,d,a-d)$ where $a,d\neq 0$, $d\neq a$ and $a+2d\neq 0$, since $B$ is free
of signed $<3$-sums. In this case there is no good cyclic ordering, as 3 out
of the 5 elements are equal to $a$, and two of them have to appear
consecutively.

Case $k=\ell=2$: Let $A=(a,-a)$ and $B=(b,-b)$. If $b\neq\pm a$ then
$(a,b,-a,-b)$ is a good cyclic ordering, otherwise it is impossible to order
$A.B=(a,-a,a,-a)$ diversely. ∎