More Like this

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

   https://doi.org/10.1007/s00208-022-02391-y  

   Sauermann, Lisa ( April 2022 , Mathematische Annalen)

   Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$$a_{j,1}{x}_1+\cdots +a_{j,k}{x}_k=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$$a_{j,i}\in F_p$. Suppose that$$k\ge 3m$$$k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$$a_{j,1}+\cdots +a_{j,k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$and that every$$m\times m$$$m\times m$minor of the$$m\times k$$$m\times k$matrix$$(a_{j,i})_{j,i}$$${\left(a_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$$A\subseteq F_p^n$of size$$|A|> C\cdot \Gamma ^n$$$\left|A\right|>C·{\Gamma }^n$contains a solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$$x_1,\cdots ,x_k\in A$are all distinct. Here,Cand$$\Gamma $$$\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma <p$. The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$in the solution$$(x_1,\dots ,x_k)\in A^k$$$(x_1,\cdots ,x_k)\in A^k$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$$x_1,\cdots ,x_k$are 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
2. Monotone Nondecreasing Sequences of the Euler Totient Function

   https://doi.org/10.1007/s44007-024-00115-z  

   Tao, Terence ( May 2024 , La Matematica)

   LetM(x) denote the largest cardinality of a subset of$$\{n \in \mathbb {N}: n \le x\}$$$\{n\in N:n\le x\}$on which the Euler totient function$$\varphi (n)$$$\phi \left(n\right)$is nondecreasing. We show that$$M(x) = \left( 1+O\left( \frac{(\log \log x)^5}{\log x}\right) \right) \pi (x)$$$M\left(x\right)=\left(1,+,O,\left(\frac{{(loglogx)}^5}{logx}\right)\right)\pi \left(x\right)$for all$$x \ge 10$$$x\ge 10$, answering questions of Erdős and Pollack–Pomerance–Treviño. A similar result is also obtained for the sum of divisors function$$\sigma (n)$$$\sigma \left(n\right)$.

    

   more » « less
3. The structure of the singular set in the thin obstacle problem for degenerate parabolic equations

   https://doi.org/10.1007/s00526-021-01938-2  

   Banerjee, Agnid ; Danielli, Donatella ; Garofalo, Nicola ; Petrosyan, Arshak ( April 2021 , Calculus of Variations and Partial Differential Equations)

   We study the singular set in the thin obstacle problem for degenerate parabolic equations with weight$$|y|^a$$${\left|y\right|}^a$for$$a \in (-1,1)$$$a\in (-1,1)$. Such problem arises as the local extension of the obstacle problem for the fractional heat operator$$(\partial _t - \Delta _x)^s$$${({\partial }_t-{\Delta }_x)}^s$for$$s \in (0,1)$$$s\in (0,1)$. Our main result establishes the complete structure and regularity of the singular set of the free boundary. To achieve it, we prove Almgren-Poon, Weiss, and Monneau type monotonicity formulas which generalize those for the case of the heat equation ($$a=0$$$a=0$).

    

   more » « less
4. Torsion phenomena for zero-cycles on a product of curves over a number field

   https://doi.org/10.1007/s40993-024-00519-4  

   Gazaki, Evangelia ; Love, Jonathan ( March 2024 , Research in Number Theory)

   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=C_1\times \cdots \times C_d$of 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=C_1\times C_2$of two curves over$$\mathbb {Q} $$$Q$with 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)$$$J_1\left(Q\right)\otimes J_2\left(Q\right)\stackrel{\epsilon }{\to }{\text{CH}}_0(C_1\times C_2)$is finite, where$$J_i$$$J_i$is the Jacobian variety of$$C_i$$$C_i$. Our constructions include many new examples of non-isogenous pairs of elliptic curves$$E_1, E_2$$$E_1,E_2$with 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=C_1\times \cdots \times C_d$for which the analogous map$$\varepsilon $$$\epsilon$has finite image.

    

   more » « less
5. From approximate to exact integer programming

   https://doi.org/10.1007/s10107-024-02084-1  

   Dadush, Daniel ; Eisenbrand, Friedrich ; Rothvoss, Thomas ( April 2024 , Mathematical Programming)

   Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq R^n$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap Z^n$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$$2^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$$2^{O\left(n\right)}·n^n$. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$$x^{\ast }\in (K\cap Z^n)$can be found in time$$2^{O(n)}$$$2^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$$x_i^{\ast }mod\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$$x^{\ast }$are given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$$2^{O\left(n\right)}{n}^n$algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,x\in Z^n$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O(log{u}_i+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le x_i\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$$n^n·2^{O\left(n\right)}$.

    

   more » « less