Additive combinatorics and its applications

    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.

    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.

    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$.