skip to main content

Title: Finding solutions with distinct variables to systems of linear equations over $$\mathbb {F}_p$$

Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$aj,1x1++aj,kxk=0for$$j=1,\dots ,m$$j=1,,mwith coefficients$$a_{j,i}\in \mathbb {F}_p$$aj,iFp. Suppose that$$k\ge 3m$$k3m, that$$a_{j,1}+\dots +a_{j,k}=0$$aj,1++aj,k=0for$$j=1,\dots ,m$$j=1,,mand that every$$m\times m$$m×mminor of the$$m\times k$$m×kmatrix$$(a_{j,i})_{j,i}$$(aj,i)j,iis non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$AFpnof size$$|A|> C\cdot \Gamma ^n$$|A|>C·Γncontains a solution$$(x_1,\dots ,x_k)\in A^k$$(x1,,xk)Akto the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$x1,,xkAare all distinct. Here,Cand$$\Gamma $$Γare constants only depending onp,mandksuch that$$\Gamma Γ<p. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$x1,,xkin the solution$$(x_1,\dots ,x_k)\in A^k$$(x1,,xk)Akto be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$x1,,xkare not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

more » « less
Author(s) / Creator(s):
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Mathematische Annalen
Page Range / eLocation ID:
p. 1-33
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$Quasi-NP=NTIME[n(logn)O(1)]and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$C, by showing that$\mathcal { C}$Cadmits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$C. Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$ixi. We show that for every sparsef, and for all “typical”$\mathcal { C}$C, faster#SAT algorithms for$\mathcal { C}$Ccircuits imply lower bounds against the circuit class$f \circ \mathcal { C}$fC, which may bestrongerthan$\mathcal { C}$Citself. In particular:

    #SAT algorithms fornk-size$\mathcal { C}$C-circuits running in 2n/nktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$(fC)-circuits of polynomial size.

    #SAT algorithms for$2^{n^{{\varepsilon }}}$2nε-size$\mathcal { C}$C-circuits running in$2^{n-n^{{\varepsilon }}}$2nnεtime (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$(fC)-circuits of polynomial size.

    Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJACC0THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    more » « less
  2. Abstract

    Let$$X\rightarrow {{\mathbb {P}}}^1$$XP1be an elliptically fiberedK3 surface, admitting a sequence$$\omega _{i}$$ωiof Ricci-flat metrics collapsing the fibers. LetVbe a holomorphicSU(n) bundle overX, stable with respect to$$\omega _i$$ωi. Given the corresponding sequence$$\Xi _i$$Ξiof Hermitian–Yang–Mills connections onV, we prove that, ifEis a generic fiber, the restricted sequence$$\Xi _i|_{E}$$Ξi|Econverges to a flat connection$$A_0$$A0. Furthermore, if the restriction$$V|_E$$V|Eis of the form$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$j=1nOE(qj-0)forndistinct points$$q_j\in E$$qjE, then these points uniquely determine$$A_0$$A0.

    more » « less
  3. Abstract

    Let$$(h_I)$$(hI)denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ID, the set of dyadic intervals and$$h_I\otimes h_J$$hIhJdenote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$(s,t)hI(s)hJ(t),$$I,J\in \mathcal {D}$$I,JD. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$V(δ2)of$$h_I\otimes h_J$$hIhJ,$$I,J\in \mathcal {D}$$I,JD. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$Lp[0,1]or the Hardy spaces$$H^p[0,1]$$Hp[0,1],$$1\le p < \infty $$1p<. We say that$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y)is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$D(hIhJ)=dI,JhIhJ, where$$d_{I,J}\in \mathbb {R}$$dI,JR, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$C:V(δ2)V(δ2)given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ChIhJ=hIhJif$$|I|\le |J|$$|I||J|, and$$\mathcal {C} h_I\otimes h_J = 0$$ChIhJ=0if$$|I| > |J|$$|I|>|J|, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y), there exist$$\lambda ,\mu \in \mathbb {R}$$λ,μRsuch that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$λC+μ(Id-C)approximately 1-projectionally factors throughD,i.e., for all$$\eta > 0$$η>0, there exist bounded operatorsABso thatABis the identity operator$${{\,\textrm{Id}\,}}$$Id,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$A·B=1and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$λC+μ(Id-C)-ADB<η. Additionally, if$$\mathcal {C}$$Cis unbounded onX(Y), then$$\lambda = \mu $$λ=μand then$${{\,\textrm{Id}\,}}$$Ideither factors throughDor$${{\,\textrm{Id}\,}}-D$$Id-D.

    more » « less
  4. Abstract

    For a smooth projective varietyXover an algebraic number fieldka conjecture of Bloch and Beilinson predicts that the kernel of the Albanese map ofXis a torsion group. In this article we consider a product$$X=C_1\times \cdots \times C_d$$X=C1××Cdof smooth projective curves and show that if the conjecture is true for any subproduct of two curves, then it is true forX. For a product$$X=C_1\times C_2$$X=C1×C2of two curves over$$\mathbb {Q} $$Qwith positive genus we construct many nontrivial examples that satisfy the weaker property that the image of the natural map$$J_1(\mathbb {Q})\otimes J_2(\mathbb {Q})\xrightarrow {\varepsilon }{{\,\textrm{CH}\,}}_0(C_1\times C_2)$$J1(Q)J2(Q)εCH0(C1×C2)is finite, where$$J_i$$Jiis the Jacobian variety of$$C_i$$Ci. Our constructions include many new examples of non-isogenous pairs of elliptic curves$$E_1, E_2$$E1,E2with positive rank, including the first known examples of rank greater than 1. Combining these constructions with our previous result, we obtain infinitely many nontrivial products$$X=C_1\times \cdots \times C_d$$X=C1××Cdfor which the analogous map$$\varepsilon $$εhas finite image.

    more » « less
  5. Abstract

    A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$(a1,a2,,an)whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$b1b2bnsatisfies$$b_i \le i$$bii. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$Rn, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$x-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$x=(a,b,,b), which we refer to as$${\textbf{x}}$$x-parking function polytopes. We explore connections between these$${\textbf{x}}$$x-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$x-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    more » « less