| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

1. Polynomial method

    1. Rudin’s problem for $\mathbb{F}_p[x], p>2$

      Problem 1.1.

      [Brandon Hanson] Suppose $A\subset \mathbb{F}_p[x]$ is of finite size, and every element of $A$ is a square. Show that $|A+A|\geq |A|^{1+\epsilon}$ for some constant $\epsilon$.
          We know that Ruzsa’s modeling theorem, and $4AP$ conjecture, implies the given problem.
        • 3APs in sets of small growth

          Problem 1.2.

          [Brandon Hanson] Obtain a proof of the following theorem using the polynomial method.

          Theorem. There is an absolute constant $c>0$ that the following holds. If $A\subset \mathbb{F}_p^n$ and $|A+A|\leq |A|^{1+c}$ then $A$ contains a 3AP.
              The current proof uses Ruzsa’s modeling lemma.
            • Polynomial method via tensorizing

                  The purpose of this problem is to extend the current polynomial method techniques to handle 4APs and more complicated patterns. It’s about suggesting a notion of tensor rank that tensorizes. Let $\mathbb{F}$ be a field and $A\in \mathbb{F}^{n\times \cdots \times n}$ be a $d$-dimensional tensor. We can think of $A$ as a multilinear polynomial $f:(\mathbb{F}^n)^d\rightarrow \mathbb{F}$ on variables $X_1,\cdots,X_d \in \mathbb{F}^n$ where $A$ specifies the coefficients of the monomials. In the following we introduce several notions of rank. Let $rank(A)$ be the minimum number of rank-one tensors that sum up to $A$. We need to specify the definition of a rank-one tensor. There are several definitions of a rank-1 tensor $f$.

              $rank$-1: $$f(X_1,\cdots,X_d) = g_1(X_1)\cdots g_d(X_d)$$ where each $g_i:\mathbb{F}^n\rightarrow\mathbb{F}$ is linear

              $srank$-1: There is some $i\in [d]$ so that $$f(X_1,\cdots,X_d) = g(X_i)f'(X_1,\cdots,X_d)$$ where $g$ is linear and $f'$ does not depend on $X_i$.

              $prank$-1: There is a subset $\phi\neq S\subset[d]$ so that $$f(X_1,\cdots,X_d) = g(X_i: i\in S) h(X_i: i\notin S)$$ Note that $prank(\cdot)\leq srank(\cdot)\leq rank(\cdot)$. We introduce another notion of rank (only for $\mathbb{F}_p$, where $p$ is prime) called analytic rank. Let $$Bias (f) = \mathbb{E}_{X_1,\cdots,X_d} \omega^{f(X_1,\cdots,X_d)}$$ where $\omega$ is a $p$th root of unity. Also note that $Bias(f)\in [0,1]$. Define $$arank(f) = -\log Bias(f).$$ We have that $arank(\cdot)\leq prank(\cdot)$.

              Now, let’s see how these notions of rank are used to solve, say the capset problem. The idea is that the identity tensor has high rank for all definitions of $arank,srank,prank$, but the capset tensor has low rank. The capset tensor is $C\in \mathbb{F}_3^{n\times n \times n}$ where $n= 3^k$ for some $k$. Given $x,y,z\in \mathbb{F}_3^k$ we have $C(x,y,z)= 0 $ if $x+y+z\neq 0$ and is 1 otherwise. If $S\subset \mathbb{F}_3^k$ is $AP$-free, then $C_{|S}$ ($C$ restricted to the set $S$) is identity.

              Problem 1.3.

              [Shachar Lovett] Let $\mathbf{r}$ be either $arank$ or $prank$. Let $A$ be a tensor, and $Id$ is the identity tensor on the same space as $A$. Suppose $\mathbf{r}(A)< \mathbf{r}(Id)$. Is it true that $\mathbf{r}(A^{\otimes m}) < \mathbf{r}(Id)^m c^m$ for some constant $c<1$?
                  This is known if $\mathbf{r}$ is chosen to be $srank$. Also, this problem, if true, has several consequences such as exponential upper bounds on size of $4AP$-free sets. More generally, it would be great to find any useful notion of rank that tensorizes.
                • Arithmetic removal lemma for cyclic groups

                      The arithmetic removal lemma is the following. $\forall\varepsilon>0, \exists\delta>0$ such that if $G$ is an abelian group and $A,B,C\subset G$, and suppose there are at least $\delta|G|^2$ solutions to $a+b+c=0, a\in A, b\in B, c\in C$. Then you can remove $\varepsilon|G|$ elements from each of the sets $A,B,C$ so that there are no solutions to $a+b+c=0$. In the case of $G = \mathbb{F}_p^n$ we know $\delta = \varepsilon^{c_p+o(1)}$ where $c_p$ is a known absolute constant and this is sharp. In the case of cyclic groups, we know that because of Behrend’s construction $\delta$ can not be a polynomial in $\varepsilon$. The known bound is however is of tower type.

                  Problem 1.4.

                  [Jacob Fox] Obtain improved bound for arithmetic regularity lemma for cyclic groups.
                      Suppose we have three sets $A=\{a_i: 1\leq i\leq n\},B=\{b_i: 1\leq i\leq n\},C= \{c_i: 1\leq i\leq n\}\subset G$. This triple is called tri-colored sumfree if $$a_i+b_j+c_k=0 \iff i=j=k.$$ Obtaining strong upper bounds on the size of tri-colored sum-free sets when $G$ is a cyclic group would possibly result in an improved arithmetic removal lemma.
                    • A polynomial method proof of Frankl-Rodl theorem

                          The Frankl-Rodl theorem is the following: let $A\subset \mathbb{F}_2^n$ be so that $A+A$ does not contain any element with hamming weight $k$ for some $k$ satisfying $C\sqrt[]{\log \alpha^{-1}n}\leq k\leq n-C\sqrt[]{\log \alpha^{-1}n}$. Then $A$ has density at most $\alpha$.

                      Problem 1.5.

                      [Shachar Lovett] Find a proof of Frankl-Rodl theorem using the polynomial method, in particular Croot-Lev-Pach method.

                          Cite this as: AimPL: Additive combinatorics and its applications, available at http://aimpl.org/addcombapp.