October 01, 2025
Note on the Additive Basis Conjecture
Yang Yu1 Date-09-30
Abstract. We show that in a vector space over \(Z_3\), the union of any four linear bases is an additive basis, thus proving the Additive Basis Conjecture for \(p=3\), and providing an alternative proof of the weak 3-flow conjecture.
Introduction
The Additive Basis Problem is a classical problem in additive combinatorics whose history parallels that of the more famous Arithmetic Progressions Problem. Both have been extensively studied since the 1930’s (see e.g. [Erdős]), first for the integers, but later also for other abelian groups; see e.g. [Mesh] (for arithmetic progressions) and [JLPT] (for additive bases) for early work taking this more general viewpoint.
For arithmetic progressions, recent years have seen celebrated progress on the central problem of bounding the sizes of AP-free sets in \(Z_p^n\) [CLP, EG]. But there has been no comparable breakthrough on what’s perhaps the best-known problem on additive bases in \(Z_p^n\): the following conjecture of Jaeger, Linial, Payan and Tarsi.
Recall that a multiset \(B\) is an additive basis of a vector space \(S\), if every element of \(S\) is a linear combination of elements in \(B\), with each coefficient either 0 or 1.
(The Additive Basis Conjecture [JLPT])
For any prime \(p\), there exists a constant \(c(p)\), such that in any vector space over \(Z_p\), the multiset union of any \(c(p)\) linear bases is an additive basis.
Conjecture 1 was studied in [ALM, Sz, NPT, EVLT, HQ, CKMS]. It is related to a few other problems in discrete mathematics. For example, the case \(p=3\) implies F. Jaeger’s famous weak 3 Flow Conjecture (proved by Carsten Thomassen in 2012 [Th]).
It is proved in [1] that the union of any \(c(p)\log n\) linear bases is an additive basis, where \(n\) is the dimension of the vector space. Our approach, like that of [1], is based on permanents. Define the perrank of a matrix \(M_{m\times n}\) to be the size of a largest square submatrix with nonzero permanent; if this is equal to \(m\) or \(n\), then we say \(M\) has full perrank.
[1] If \(B_1,B_2,\cdot\cdot\cdot, B_p\) are nonsingular matrices over a field of characteristic \(p\ge 3\), then \(\left(\begin{array}{cccc} B_1 & B_2 &\cdot\cdot\cdot& B_p \\ \vdots &\vdots &&\vdots \\ B_1 & B_2 &\cdot\cdot\cdot& B_p\end{array}\right)\), where each row repeats \(p-1\) times, has full perrank.
Here we give the first constant bounds for both conjectures, and in particular the first proof of any case of the Additive Basis Conjecture:
If \(P,R,S,T\) are nonsingular matrices over a field of characteristic 3, then \(\left(\begin{array}{cccc} P & R & S & T \\ P & R & S & T \end{array}\right)\) has full perrank.
Corollary 4Conjecture 1 holds for \(p = 3\), with \(c(p) = 4\).
This corollary follows from Theorem 3 by the Combinatorial Nullstellensatz (see [1] section 3 for details), while Conjecture 2 implies Conjecture 1 with \(c(p)=p\). Theorem 3 will be proved at the end of the paper, after we have developed the necessary machinery, the main point here being Theorem 7. An early look at the easy derivation of Theorem 3 should help to motivate what precedes it.
This paper is part 3 of the author’s series “The permanent rank of a matrix”; part 1 was [Yu]; and at this writing part 2 is still in preparation.
Definitions and Notation
Given a field, let \(A^n\) be the quotient of the polynomial ring in \(n\) variables
\(x_1, x_2, \cdot\cdot\cdot, x_n\) by the ideal generated by \(x_1^2,\,x_2^2, \cdot\cdot\cdot, x_n^2\). The \(k\) - th degree component of the graded algebra
\(A^n\) is denoted by \(A_k^n\); we omit \(n\) when there is no ambiguity. For an ideal \(J\subseteq A\), let \(J_k=A_k \cap J\).
For \(f\in A\), define \(\textrm{Ker}(f)=\{g:gf=0\}\), \(\textrm{Im}(f)=\{ fg: g\in A\}\).
We introduce two operators. Let \(\partial_x\) and \(E_x\) be the quotient and remainder of formal division by \(x\); we use \(\partial_i\) for \(\partial_{x_i}\) and similarly for \(E_i\). For example, if \(f=x_1x_2+x_1x_3+x_2x_3\), then \(\partial_1 f=x_2+x_3\) and \(E_1 f=x_2x_3\).
(We use the letter \(E\) because \(E_i\) eliminates all terms containing \(x_i\)).
It is obvious that \(E_i(fg)=(E_i f)(E_i g),\;\;\partial_i(fg)=(\partial_i f)(E_i g)+(\partial_i g)(E_i f)\), and \(E_i E_j=E_j E_i,\; \partial_i\partial_j=\partial_j\partial_i,\; E_i\partial_j=\partial_j E_i\) (but \(E_i \partial_j \neq E_j \partial_i\)).
For \(u\in A_1\), define its support to be supp\((u):=\{ x: \partial_x u\neq 0\}\). An element of \(A_1\) is also called a linear form.
Let \(u\) be a linear form with \(\partial_x u=c\neq 0\), set \(\partial_x=\partial, E_x=E\) for simplicity. For any \(f\), define another division operation: divide \(f\) by \(u\) w.r.t. \(x\) by
\(f=Ef+(\partial f)x=Ef+(\partial f)(u-Eu) c^{-1}=c^{-1}(\partial f)u + Ef-c^{-1}(\partial f)(Eu)\) and define \(R_{(u,\,x)} f:=Ef-c^{-1}(\partial f)(Eu)\) as the remainder.
Evidently \(\partial(R f)=0\) and \(f-Rf\in\textrm{Im}(u)\), this is what we need later.
For \(U\) and \(V\) subspaces of \(A_i\) and \(A_j\) respectively, define \(UV\) to be the subspace of \(A_{i+j}\) spanned by \(\{uv: u\in U,\;v\in V\}\). Define \(\textrm{Im}(U)\) to be the ideal generated by \(U\), and \(\textrm{Ker}(U)=\{f:fu=0\;\;\forall\,u\in U\}\).
A subspace of \(A_1\) is also called a linear form space. For a linear form space \(U\), define its support to be supp\((U):=\bigcup\limits_{u\in U}\)supp\((u)\); define its minimum support function to be
ms\(_i(U):=\) min \(\{|\,\textrm{supp}(V)|: V\subseteq U\;\textrm{with dim}(V)=i\,\}\) for \(i\le\) dim\((U)\).
Label the rows and columns of a matrix \(M_{m\times n}\) with variables \(x_1,x_2,\cdot\cdot\cdot,x_m\) and \(y_1,y_2,\cdot\cdot\cdot,y_n\) respectively, and view its rows and columns as linear forms in \(A^n\) and \(A^m\). Then \(M\) has full perrank iff the product of its rows or columns is nonzero in \(A^n\) or \(A^m\).
Supporting Results and Proofs
From now on, we assume the ground field has characteristic 3 and is infinite, otherwise extend it to infinity. The following theorem is the base step for the main induction in the proof of Theorem 7.
(1) \(\textrm{Ker}_k(u)=\textrm{Im}_k(u^2)\) for any linear form \(u\) with \(|\,\)supp\((u)|\ge 2k+1\).
(2) \(\textrm{Ker}_k(u^2)=\textrm{Im}_k(u)\) for any linear form \(u\) with \(|\,\)supp\((u)|\ge 2k+2\).
Since \(u^3=0\), one direction is trivial. The other direction is by induction on \(k\), easy to verify when \(k=1\). Pick any \(x\in\) supp\((u)\), and set \(\partial_x=\partial, E_x=E\) for simplicity. WMA \(\partialu=1\).
(1) Suppose \(f\in \textrm{Ker}_k(u),\; fu=0\); take \(\partial,\; E f+(\partial f)(E u)=0\); multiply by \(E u,\; (\partial f)(E u)^2=0\). By induction
hypothesis of (2), \(\partial f=g(E u)\) for some \(g\), then
\(f=Ef+(\partial f)x=(\partial f)(x-Eu)=-g(Eu)(Eu-x)=-g(Eu+x)^2=-gu^2\).
(2) Suppose \(f\in \textrm{Ker}_k(u^2),\; fu^2=0\); take \(\partial,\; (2Ef+(\partial f)Eu)Eu=0\). By (1) we have \(Ef-(\partial f)Eu=g(Eu)^2\) for some
\(g\), then
\(f=Ef+(\partial f)x=(\partial f)(Eu+x)+g(Eu)^2=(\partial f)u+gu(Eu-x)\in\textrm{Im}(u)\).
We say a linear form space \(U\) covers \((a_1,a_2,\cdot\cdot\cdot,a_k)\) if ms\(_i(U)\ge a_i\) for all \(1\le i\le k\).
The following lemma plays a crucial role in the proof of Theorem 7.
Suppose \(U\) is a linear form space with dim\((U)=n\) covering an increasing sequence \((a_1,a_2,\cdot\cdot\cdot,a_n)\). Then for each \(0\le k\le n\), there exists a subspace \(U_k\subseteq U\) with dim\((U_k)=k\) covering \((a_{n+1-k}, a_{n+2-k}, \cdot\cdot\cdot, a_n)\).
Proof. Set \(U_0=0\) and suppose \(U_k\) exists.
For each \(S\subseteq\) supp\((U)\) with \(|S|=a_{n-k}-1\), let
\(V_S:=\{v : v\in U,\textrm{ there exists }\,u\in U_k\,\textrm{ such that supp}(v+u)\subseteq S\}\);
note \(U_k\subseteq V_S\) since supp\((0)=\varnothing\). Claim \(V_S\) is a proper subspace of \(U\), otherwise choose \(\{v_i\}\) such that \(U=\) span\((U_k, v_1, v_2, \cdot\cdot\cdot, v_{n-k})\). For each \(i\), choose \(u_i\in U_k\) such that supp\((v_i+u_i)\subseteq S\). Let \(V=\) span\((\{v_i+u_i\})\), then dim\((V)=n-k,\, |\,\)supp\((V)|<a_{n-k}\), contradiction.
Because the ground field is infinite, \(U\) is not a finite union of its proper subspaces. Choose \(v\in U\) that is not in any \(V_S\), and let \(U_{k+1}:=\) span\((U_k, v)\).
If \(u\in U_{k+1}\backslash U_k, \textrm{then }|\) supp\((u)|\ge a_{n-k}\) by our choice of \(v\). If \(0\neq u\in U_k\), then by induction hypothesis, \(|\) supp\((u)|\ge\) ms\(_1(U_k)\ge a_{n+1-k}>a_{n-k}\). So ms\(_1(U_{k+1})\ge a_{n-k}\).
For any \(H\subseteq U_{k+1}\) with dim\((H)=h\ge 2\), either dim\((H\cap U_k)=h-1\) or \(H\subseteq U_k\). By induction hypothesis, either
\(|\) supp\((H)|\ge |\,\)supp\((H\cap U_k)|\ge\) ms\(_{h-1}(U_k)\ge a_{n+h-1-k}\), or
\(|\) supp\((H)|\ge\) ms\(_h(U_k)\ge a_{n+h-k}>a_{n+h-k-1}\).
So ms\(_h(U_{k+1})\ge a_{n+h-k-1}\).
Suppose \(U\) is a linear form space, dim\((U)=n\) and \(k\ge0\).
(A) If ms\(_i(U)\ge 4i-2+2k\) for \(1\le i\le n\), then \(\textrm{Ker}_k(U^{2n})=\textrm{Im}_k(U)\).
(B) If ms\(_i(U)\ge 4i-3+2k\) for \(1\le i\le n\), then
\(\textrm{Ker}_{2n-2+k}(U)=\textrm{Im}_{2n-2+k}(U^{2n})\).
The proof is delicate, any mismatch between degree and support or other discrepancy invalidates it. We need to check degree and support (abbrev. CDS) 8 times; 5 times exact match; 3 times there is extra support of exactly one. The induction hypothesis is applied 6 times in the proof.
Proof. One direction is trivial, the other direction is by induction on \(n\). Theorem 5 gives the case \(n=1\). Suppose true for \(n-1\), then induction on \(k\) by: \(B(n,0)\longrightarrow A(n,0)\longrightarrow B(n,1)\longrightarrow A(n,1)\longrightarrow B(n,2)\longrightarrow A(n,2) \cdot\cdot\cdot\cdot\)
Claim: \(A(n,k-1)\) implies \(B(n,k)\) for all \(k\ge 1\).
Suppose \(U\) satisfies condition (B) and \(f\in\textrm{Ker}_{2n-2+k}(U)\). By Lemma 6, there exists \(V\subseteq U\) with dim\((V)=n-1\), and ms\(_i(V)\ge 4i+1+2k\) for all \(1\le i\le n-1\).
Choose a variable \(x\) and a linear basis \(\{u_1+x, u_2,u_3,\cdot\cdot\cdot, u_{n-1}\}\) of \(V\) such that \(\partial_x u_i=0\) for all \(1\le i\le n-1\). Choose any \(u\in U\backslash V\) and let \(u_n=R_{(u_1+x,\,x)} u\). Then \(\partial_x u_n=0\) and \(\{u_1+x, u_2,\cdot\cdot\cdot, u_n\}\) is a linear basis of \(U\). Note \(2n-2+k=2(n-1)-2+(k+2)\), and \(f\in\textrm{Ker}_{2n-2+k}(V)\) also. Apply \(B(n-1,k+2)\) to \(V\), CDS exact match. We get
\(f=g(u_1+x)^2 u_2^2 \cdot\cdot\cdot u_{n-1}^2\) (1)
for some \(g\) with deg\((g)=k\). WMA \(\partial_x g=0\), otherwise replace it with \(R_{(u_1+x,\,x)}g\). Then \(fu_n=0\) gives \(g u_n (u_1+x)^2 u_2^2 \cdot\cdot\cdot u_{n-1}^2=0\).
Apply \(A(n-1,k+1)\) to \(V\), CDS extra support of one. We have
\(gu_n=a_1(u_1+x)+a_2 u_2+\cdot\cdot\cdot+a_{n-1}u_{n-1}\) for some \(a_i\).
If \(k=0\), then \(g=a_i=0,\; f=0\). Here we got \(B(n,0)\).
If \(k\ge 1\), multiply above by \((u_1+x)^2\). Let \(b_i=R_{(u_1+x,\,x)} a_i\), we get
\(g u_n(u_1+x)^2=b_2 u_2(u_1+x)^2+\cdot\cdot\cdot+b_{n-1}u_{n-1}(u_1+x)^2\). Then take \(\partial_x\), we get \(g u_n u_1=b_2 u_2 u_1+\cdot\cdot\cdot+b_{n-1}
u_{n-1} u_1\). Apply Theorem 5(1) to \(u_1\), deg\((g u_n)=k+1,\, u_1+x\in V,\; |\,\)supp\((u_1)|\ge 2k+4\), CDS extra support of one. We have \(g u_n =b_2 u_2 +\cdot\cdot\cdot+b_{n-1} u_{n-1}+d u_1^2\)(2)
for some \(d\) with deg\((d)=k-1\).
Multiply by \(u_2^2\cdot\cdot\cdot u_{n-1}^2 u_n^2\), we get \(d u_1^2 u_2^2\cdot\cdot\cdot u_n^2=0\).
Since ms\(_1(U)\ge 1+2k\ge 3\), \(x\notin U\), so dim\((E_x(U))=n\). Apply \(A(n,k-1)\) to \(E_x(U)\), CDS exact match. We get \(d=c_1 u_1+c_2 u_2+\cdot\cdot\cdot+c_n u_n\). Substitue into (2), we get \((g-c_n u_1^2)u_n\in\textrm{Im}(\)span\((u_2, \cdot\cdot\cdot, u_{n-1}))\).
Multiply by \(u_2^2\cdot\cdot\cdot u^2_{n-1}\), we get \((g-c_n u_1^2)u_2^2\cdot\cdot\cdot u_{n-1}^2 u_n=0\). Introduce a dummy variable \(y\) to make \((g-c_n u_1^2) u_2^2\cdot\cdot\cdot u_{n-1}^2 (u_n+y)^2=0\).
Let \(Y:=\) span\((u_2,\cdot\cdot\cdot, u_{n-1}, u_n+y)\). For any \(I\subseteq Y\) with dim\((I)=i\), if \(y\notin\) supp\((I)\), then \(I\subseteq\) span\((u_2,\cdot\cdot\cdot, u_{n-1})\subseteq V\) with \(|\,\)supp\((I)|\ge 4i+1+2k\). If \(y\in\) supp\((I)\), then \(|\,\)supp\((E_y(I))|\ge 4i-3+2k\) since \(E_y(I)\subseteq U\), and so \(|\,\)supp\((I)|\ge 4i-2+2k\). Apply \(A(n-1,k)\) to \(Y\), CDS exact match. We have \(g-c_n u_1^2\in\textrm{Im}(Y)\). Take \(E_y\), we get \(g-c_n u_1^2\in\textrm{Im}(U)\); then \(g\in\textrm{Im}(U)\) since \(u_1^2=(u_1+x)(u_1-x)\).
Substitute \(g\in\textrm{Im}(U)\) into (1), we get \(f=h u_n (u_1+x)^2 u_2^2 \cdot\cdot\cdot u_{n-1}^2\)(3)
for some \(h\) with deg\((h)=k-1\). Then \(f u_n=0\) gives
\(h u_n^2 (u_1+x)^2 u_2^2 \cdot\cdot\cdot u_{n-1}^2=0\).
Apply \(A(n,k-1)\) to \(U\), CDS extra support of one. If \(k=1\), then \(h=0,\; f=0\). If \(k\ge 2\), we have \(h\in\textrm{Im}(U)\). Substitute into (3), we get \(f=p u_n^2 (u_1+x)^2 u_2^2 \cdot\cdot\cdot u_{n-1}^2\) for some \(p\). That is, \(f\in\textrm{Im}_{2n-2+k}(U^{2n})\).
Claim: \(B(n,k)\) implies \(A(n,k)\) for all \(k\ge 0\).
Suppose \(U\) satisfies condition (A) and \(f\in \textrm{Ker}_k(U^{2n})\). Choose a variable \(x\) and a linear basis \(\{u_1+x,
u_2,u_3,\cdot\cdot\cdot, u_n\}\) of \(U\) such that \(\partial_x u_i=0\) for all \(1\le i\le n\). Observe \(U^{2n}=\) span\(((u_1+x)^2 u_2^2 \cdot\cdot\cdot u_n^2)\). Let \(g=R_{(u_1+x,\,x)} f\), then \(g\in\textrm{Ker}_k(U^{2n})\)
also. Take \(\partial_x\) to \(g(u_1+x)^2 u_2^2 \cdot\cdot\cdot u_n^2=0\), we get
\(g u_1 u_2^2 \cdot\cdot\cdot u_n^2=0\). So \(g u_2^2 \cdot\cdot\cdot u_n^2\in \textrm{Ker}_{2n-2+k}(E_x (U))\).
Since ms\(_1(U)\ge 2\), \(x\notin U\), so dim\((E_x(U))=n\). Apply \(B(n,k)\) to \(E_x (U)\), CDS exact match. We have \(g u_2^2 \cdot\cdot\cdot u_n^2\in \textrm{Im}_{2n-2+k}(E_x (U)^{2n})\).
So \(g u_2^2 \cdot\cdot\cdot u_n^2=0\) when \(k\le 1\); and \(g u_2^2 \cdot\cdot\cdot u_n^2=h u_1^2 u_2^2 \cdot\cdot\cdot u_n^2\) for some \(h\) when \(k\ge 2\), then \((g-h u_1^2)u_2^2 \cdot\cdot\cdot u_n^2=0\).
Apply \(A(n-1,k)\) to span\((u_2,\cdot\cdot\cdot, u_n)\subseteq U\), CDS exact match.
When \(k\ge 2\), we have \(g-h u_1^2\in\textrm{Im}(U)\). Since \(u_1^2=(u_1+x)(u_1-x)\), \(g\in\textrm{Im}(U),\, f\in\textrm{Im}(U)\). When \(k=1,\, g\in\textrm{Im}(U),\, f\in\textrm{Im}(U)\). When \(k=0,\, g=0,\, f=0\).
Proof of Theorem 3: Let \(U\) be the linear form space spanned by the rows of \((P\; R\; S\; T)_{n\times 4n}\), then ms\(_i(U)\ge 4i\) for all \(1\le i\le n\). By applying Theorem 7 (A) with \(k=0\), we have \(U^{2n}\neq 0\). That is, \(\left(\begin{array}{cccc} P & R & S & T \\ P & R & S & T\end{array}\right)\) has full perrank.
Acknowledgements The author would like to thank Noga Alon, Micha Christoph, Jeff Kahn, Noah Kravitz and Peter Pach for their comments on this paper.
References
contact: yang.yu30@rutgers.edu, Dept of Math, Rutgers University↩︎