% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: \usepackage{amsmath,amssymb} % We recommend the graphicx package for importing figures: \usepackage{graphicx} % Use this command to create hyperlinks (optional and recommended): \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{tikz} \newcommand*\circled[1]{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=1pt] (char) {#1};}} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{June 20, 2018}{October 23, 2018}{TBD} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05D05 , 05E99} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{Zeev Dvir and Shay Moran. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{A Sauer-Shelah-Perles Lemma for Sumsets} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. \def\Z{{\mathbb{Z}}} \def\N{{\mathbb{N}}} \def\R{{\mathbb{R}}} \def\F{{\mathbb{F}}} \def\cM{{\cal M}} \def\VC{\textsf{VC-dim}} \def\intdeg{\textsf{int-deg}} \def\symdif{{\triangle}} \def\rank{\textsf{rank}} \newcommand{\eps}{\epsilon} \author{Zeev Dvir\thanks{Research supported by NSF CAREER award DMS-1451191 and NSF grant CCF-1523816.}\\ \small Department of Computer Science and Department of Mathematics\\[-0.8ex] \small Princeton University\\[-0.8ex] \small Princeton, U.S.A.\\ \small\tt zeev.dvir@gmail.com\\ \and Shay Moran\thanks{Research supported by the National Science Foundation under agreement No. CCF-1412958 and by the Simons Foundations.}\\ \small School of Mathematics\\[-0.8ex] \small Institute for Advanced Study\\[-0.8ex] \small Princeton, U.S.A.\\ \small\tt shaymoran1@gmail.com} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} We show that any family of subsets $A\subseteq 2^{[n]}$ satisfies $\lvert A\rvert \leq O\bigl(n^{\lceil{d}/{2}\rceil}\bigr)$, where $d$ is the VC dimension of $\{S\triangle T \,\vert\, S,T\in A\}$, and $\triangle$ is the symmetric difference operator. We also observe that replacing $\symdif$ by either $\cup$ or $\cap$ fails to satisfy an analogous statement. Our proof is based on the polynomial method; specifically, on an argument due to [Croot, Lev, Pach '17]. \end{abstract} \section{Introduction} Let $A \subset 2^{[n]}$ be a family of subsets of an $n$ element set ($[n]$ w.l.o.g). The VC dimension of $A$, denoted by $\VC(A)$, is the size of the largest $Y\subseteq [n]$ such that $\{S\cap Y \,\vert\, S\in A\} = 2^{Y}$. One of the most useful facts about the VC dimension is given by the Sauer-Shelah-Perles Lemma. \begin{theorem}[Sauer-Shelah-Perles Lemma \cite{sauer72density,shelah72comb}]\label{thm:sauer} Let $d\leq n\in\N$. Suppose $A \subset 2^{[n]}$ satisfies $\VC(A) \leq d$. Then $\lvert A\rvert \leq {n \choose \leq d}$. \end{theorem} The Sauer-Shelah-Perles Lemma has numerous applications ranging from model theory, probability theory, geometry, combinatorics, and various fields in computer science. A simple-yet-useful corollary of this lemma is that if $\VC(A) \leq d$, and $\star$ is any binary set-operation (e.g.\ $\star\in\{\cap,\cup,\symdif\}$) then \[\bigl\lvert\{ S\star T \,\vert\, S,T\in A\}\bigr\rvert \leq {n \choose \leq d}\cdot{n \choose \leq d} = O(n^{2d}).\] This corollary is used, for example, by~\cite{blumer89VC} to derive closure properties for {\it PAC learnability}. Let~$A{\circled{$\star$}} A$ denote the family $\{ S\star T \,\vert\, S,T\in A\}$. In this work we explore the converse direction: Does an upper bound on the VC-dimension $\VC(A\circled{$\star$} A)$ imply an upper bound on~$\lvert A\rvert$? It is not hard to see that $\VC(A)\leq\VC(A\circled{$\star$} A)$ for $\star\in\{\cup,\cap,\symdif\}$, and therefore, by Theorem~\ref{thm:sauer}: $\VC(A\circled{$\star$} A) < d\implies \lvert A\rvert\leq O(n^d)$. Our main result quadratically improves this naive bound when $\star$ is symmetric difference: \begin{theorem}\label{thm-main} Let $d\leq n\in\N$. Suppose $A \subset 2^{[n]}$ satisfies $\VC(A \circled{$\symdif$} A) \leq d$. Then \[\lvert A\rvert \leq 2 {n \choose \leq \lfloor {d}/{2}\rfloor}.\] \end{theorem} We note that Theorem~\ref{thm-main} does not hold when $\star\in\{\cup,\cap\}$: pick $d\geq 2$, and set \[ A = \{ S \subseteq [n] \,\vert\, \lvert S\rvert \leq d\}.\] Note that $A = A\circled{$\cap$} A $ and therefore $d =\VC(A)= \VC(A\circled{$\cap$} A)$. However $\lvert A \rvert = {n \choose \leq d} = \Theta(n^d)$, which is not upper bounded by $O(n^{\lceil {d}/{2}\rceil})$. Picking $A = \{ S \subseteq [n] \,\vert\, \lvert S\rvert \geq n-d\}$ shows that~$\cup$ behaves similarly to $\cap$ in this context. The above examples rule out the analog of Theorem~\ref{thm-main} for exactly one of $\cup,\cap$. This suggests the following open question: \begin{question} Let $d\leq n\in\N$. Suppose $A \subset 2^{[n]}$ satisfies $\VC(A\circled{$\cap$} A) \leq d$ and $\VC(A\circled{$\cup$} A) \leq d$. Is it necessarily the case that $\lvert A\rvert \leq n^{{d}/{2} + O(1)}$? \end{question} Another natural question is whether this phenomenon extends to several applications of the symmetric difference operator, for example: \begin{question} Does there exist an $\eps < 1/2$ such that for every $d\leq n$ and every $A\subset 2^{[n]}$: \[ \VC\bigl(A\circled{$\triangle$} A \circled{$\symdif$} A\bigr)\leq d \implies \lvert A\rvert \leq n^{\eps \cdot d + O(1)}?\] \end{question} {In Section~\ref{sec:modp} we derive a related statement when $\symdif$ is replaced by addition modulo $p$ for a prime~$p$, and the VC dimension is replaced by the interpolation degree (which is defined in the next section).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Interpolation degree} Since our proof method is algebraic, it is convenient to view $A\subset 2^{[n]}$ as a subset of the $n$-dimensional vector space $\F_2^n$ over the field of two elements. In this setting $A \circled{$\symdif$}A$ is the {\em sumset} of $A$, denoted~$A+A$. % Since our proof method is algebraic, for the rest of the paper we will think of $A$ in this manner as a subset of $\F_2^n$. Theorem~\ref{thm-main} will follow from a stronger statement involving a quantity referred to in some places as the {\em regularity} (as a special case of Castelnuovo-Mumford regularity from algebraic geometry)~\cite{Remscrim16} and in others as the {\em interpolation-degree} \cite{moran16shattered}. We will use the more descriptive interpolation-degree for the rest of this paper. We begin with some preliminary notations and definitions. Let $A \subset \F_2^n$. It is a basic fact that for each function $f : \F_2^n \mapsto \F_2$ there exists a unique multilinear polynomial $P_f \in \F_2[x_1,\ldots,x_n]$ such that $f(a) = P_f(a)$ for all $a\in \F_2^n$ (existence is via simple interpolation and uniqueness follows from dimension counting). For a partial function $f : A \mapsto \F_2$ there are many (precisely $2^{{2^n - |A|}}$) multilinear polynomials whose restriction to $A$ computes $f$. Let $\deg_A(f)$ denote the minimal degree of any polynomial whose restriction to $A$ computes $f$. We define the {\em interpolation-degree} of $A$, denoted $\intdeg(A)$ to be the maximum of $\deg_A(f)$ taken over all functions $f : A \mapsto \F_2$. In other words, $\intdeg(A)$ is the smallest $d$ such that any function from $A$ to $\F_2$ can be realized by a polynomial of degree at most $d$. Clearly, $\intdeg(A)$ is an integer between $0$ and $n$. It is also not hard to see that, if $A$ is a proper subset of ${\F_2^n}$ then $\intdeg(A) < n$. Our interest in $\intdeg(A)$ comes from the following connection to VC-dimension. \begin{lemma}[\cite{babai92book,gurvits97linear,smolensky97vc,moran16shattered}]\label{thm:intdegvc} For $A \subset \F_2^n$ we have $\intdeg(A) \leq \VC(A)$. \end{lemma} This Lemma, under various formulations, was proved in several works. The formulation that appears here can be found in \cite{moran16shattered}. For completeness, we next sketch the proof: since the set of all multilinear monomials (also those of degree larger than $\VC(A)$) span the set of functions $f: A\to\F_2$, it suffices to show that any monomial (when seen as an $A\to \F_2$ function) can be represented a polynomial of degree at most $d=\VC(A)$. The crucial observation is that if $x_S = \pi_{i\in S} x_i$ is a monomial of degree larger than $d$, then $S$ is not shattered by $A$. This means that there is a pattern $v:S\to\{0,1\}$ that does not appear in any of the vectors in $A$ and therefore \[ \Pi_{i\in S}(x_i + v_i + 1) =_{A} 0,\] where ``$=_A$'' means equality as functions over $A$. Now, expanding this product and rearranging the equation yields a representation of $x_S$ as sum of monomials~$x_{S'}$, where $S' \subset S$, which by induction can also be represented by polynomials of degree at most $d$. Theorem~\ref{thm:intdegvc} reduces Theorem~\ref{thm-main} to the following stronger statement that is proved in the next section. \begin{theorem}\label{thm-intdeg} Let $d\leq n\in\N$, and let $A \subset \F_2^n$ satisfy $|A| > 2{n \choose \leq \lfloor{d}/{2} \rfloor}$. Then $\intdeg(A+A) > d$. \end{theorem} \section{Proof of Theorem~\ref{thm-intdeg}} The main technical tool will be a lemma of Croot-Lev-Pach \cite{CLP17} that was the main ingredient in the recent solution of the cap-set problem \cite{EG17} and has found many other applications since then (e.g., \cite{Green16, Soly18, DB17, Fox17} to name a few). \begin{lemma}[CLP lemma \cite{CLP17}]\label{lem-clp} Let $P \in \F_q[x_1,\ldots,x_n]$ be a polynomial of degree at most $d$ over any finite field $\F_q$, and let $M$ denote the $q^n \times q^n$ matrix with entries $M_{x,y} = P(x+y)$ for $x,y \in \F_q^n$. Then $\rank(M) \leq 2\cdot m_{\lfloor d/2 \rfloor}(q,n),$ where $m_{k}(q,n)$ denotes the number of monomials in $n$ variables $x_1,\ldots,x_n$ such that each variable appears with individual degree at most $q-1$ and the total degree of the monomial is at most $k$. \end{lemma} Specializing to our setting of $\F_2$ multilinear polynomials, we see that $m_k(2,n) = {n \choose \leq k}$ and so we conclude: \begin{corollary}\label{cor-clp} Let $P \in \F_2[x_1,\ldots,x_n]$ be a polynomial of degree at most $d$ and let $M$ be as in Lemma~\ref{lem-clp}. Then $\rank(M) \leq 2 {n \choose \leq \lfloor d/2 \rfloor}$. \end{corollary} We are now ready to prove Theorem~\ref{thm-intdeg}. \begin{proof}[Proof of Theorem~\ref{thm-intdeg}] Suppose $A \subset \F_2^n$ is such that $|A| \geq 2{n \choose \leq \lfloor{d}/{2}\rfloor}$. Let $f : A+A \mapsto \F_2$ be such that $f(\bar 0)=1$, where $\bar 0$ is the all zero vector in $\F_2^n$, and $f(a)=0$ for all non-zero $a \in A+A$. It suffices to show that $deg_{A+A}(f)\geq \lfloor{d}/{2}\rfloor$ ({notice that since $A\neq\emptyset$} it follows that $\bar 0\in A+A$ and so~$f$ is not constantly $0$ on $A+A$). Let $M$ be the $2^n \times 2^n$ matrix whose rows and columns are indexed by $\F_2^n$ and with entries $M_{x,y} = f(x+y)$. By our definition of $f$ we have that the sub-matrix of $M$ whose rows and columns are indexed by $A$ is just the $|A|\times |A|$ identity matrix. This implies $$ \rank(M) \geq |A|.$$ Let $d_f = \deg_{A+A}(f)$ denote the smallest degree of a polynomial whose restriction to $A+A$ computes~$f$. Applying Corollary~\ref{cor-clp} we get that \[ \rank(M) \leq 2{ n \choose \leq \lfloor d_f/2 \rfloor}.\] Combining the two inequalities on $\rank(M)$ and using the bound on the size of $A$ we get that \[2{n \choose \leq \lfloor{d}/{2}\rfloor} < |A| \leq \rank(M) \leq 2{ n \choose \leq \lfloor d_f/2 \rfloor}, \] which implies $\lfloor d/2 \rfloor < \lfloor d_f/2 \rfloor$. This means that $d_f > d$ and so $\intdeg(A+A) > d$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Generalization to sums modulo $p$}\label{sec:modp} In this section we observe that our proof can be generalized to give stronger bounds in the case when we take $p$-fold sums of boolean vectors over $\F_p$. The case proved in the last section corresponds to (two fold) sums modulo 2. For a subset $A \subset \F_p^n$ and a positive integer $k$, we denote by $$k\cdot A = \{ a_1 + \ldots + a_k \,|\, a_i \in A \}$$ the $k$-fold sumset of $A$. To formally define the interpolation degree over $\F_p$ we need to consider, instead of multilinear polynomials, polynomials in which each variable has degree at most $p-1$. We call such polynomials {\em $p$-reduced} polynomials. The space of all $p$-reduced polynomials has dimension $p^n$ and can uniquely represent any function $f: \F_p^n \mapsto \F_p$. The degree of such a function is defined to be the total degree of the unique $p$-reduced polynomial representing it and can range between 0 and $(p-1)n$. The interpolation degree of a set $A \subset \F_q^n$ is the minimum $d$ such that any function $f : A \mapsto \F_p$ can be represented by a $p$-reduced polynomial of degree at most $d$. To avoid confusion we will denote the interpolation degree over $\F_p^n$ as $\intdeg_p(A)$. We denote by $\cM_d(p,n)$ the set of monomials in $n$ variables $x_1,\ldots,x_n$ in which each variable has degree at most $p-1$ and the total degree is at most $d$. When $p=2$ we have the closed formula $|\cM_d(2,n)| = {n \choose \leq d}$. When $p >2$ the quantity $|\cM_d(p,n)|$ is a bit more tricky to compute but is known to satisfy certain asymptotic inequalities (e.g., large deviations \cite{LDP15} showing that $\cM_{\delta n}(p,n) \leq 2^{\eps n}$ with $\eps(\delta)$ going to zero with $\delta$). The following theorem generalizes Theorem~\ref{thm-main} when $p > 2$. \begin{theorem}\label{thm-psums} Let $p$ be any prime number and let $A \subset \{0,1\}^n \subset \F_p^n$ be such that $|A| > p\cdot |\cM_{\lfloor d/p \rfloor}(p,n)|$. Then $\intdeg_p(p \cdot A) > d$. \end{theorem} The proof of the theorem requires the notion of {\em slice-rank} of a tensor which was introduced by Tao in his symmetric interpretation of the proof of the cap-set conjecture \cite{Tao-capset}. By a $k$-fold tensor of dimension $D$ over a field $\F$ we mean a function $T$ mapping ordered tuples $(j_1,\ldots,j_k) \in [D]^n$ to $\F$. The {\em slice-rank} of a $k$-fold tensor $T$ is a the smallest integer $R$ such that $T$ can be written as a sum $T = \sum_{i=1}^R T_i$ such that, for every $i \in [R]$ there is some $j_i \in [k]$ so that $T_i(j_1,\ldots,j_k)= A(j_i)B(j_1,\ldots,j_{i-1},j_{i+1},\ldots,j_k)$. In other words, we define the `rank one' tensors to be those in which the dependence on one of the variables is multiplicative (by a function $A(j_i)$) and the rank of a tensor is the smallest number of rank one tensors needed to describe it. For 2-fold tensors (or matrices) this notion coincides with the usual definition of matrix rank. The proof of Theorem~\ref{thm-psums} will follow from a combination of two lemmas regarding slice rank. The first lemma generalizes the Croot-Lev-Pach lemma (and proved in an a similar way). \begin{lemma}\label{lem-clpmodp} Let $f : \F_p^n \mapsto \F_p$ be of degree $d$. Then the $p$-fold $p^n$ dimensional tensor $T: (\F_p^n)^k \mapsto \F_p$ defined by $T(X^1,\ldots,X^p) = f(X^1 + \ldots +X^p)$ has slice rank at most $p\cdot \cM_{\lfloor d/p \rfloor}(p,n)$. \end{lemma} \begin{proof} Consider $T$ as a polynomial in $p$ groups of variables $X^i = (x^i_1,\ldots,x^i_n)$ with $i = 1,2,\ldots,p$. Since the degree of $f$ is $d$, the degree of $T$ as a polynomial will also be at most $d$. This means that, in each monomial of $T(X^1,\ldots,X^p) = f(X^1 + \ldots +X^p)$, the degree of at least one group of variables will be at most $\lfloor d/p \rfloor$. Grouping together monomials according to which group has low degree (if there is more than one group take the one with lowest index) we can represent $T$ as a sum of $p$ tensors, each having rank at most $\cM_{\lfloor d/p \rfloor}(p,n)$. This completes the proof. \end{proof} The second lemma needed to prove Theorem~\ref{thm-psums} is due to Tao and shows that the 'diagonal' tensor has full rank. \begin{lemma}[\cite{Tao-capset}]\label{lem-taorank} Let $\delta(j_1,\ldots,j_k): [D]^k \mapsto \F$ be defined as $\delta(j,j,\ldots,j) = 1$ for all $j$ and is zero otherwise. Then the slice rank of $\delta$ is equal to $D$. \end{lemma} \begin{proof}[Proof of Theorem~\ref{thm-psums}] To prove the bound on $\intdeg_p(p\cdot A)$ we describe a function $f : p\cdot A \mapsto \F_p$ that cannot be represented by a low degree polynomial. We take $f$ to be equal to $1$ on the zero vector and zero otherwise. We now consider the tensor $T(X^1,\ldots,X^p) = f(X^1 + \ldots +X^p)$ defined on $A^p$. Notice that, since $A \subset \{0,1\}^n$, the sum of $p$ of them is equal to zero iff all $p$ summands are identical. This implies that $T$ is the diagonal tensor $\delta$ of Lemma~\ref{lem-taorank} and hence has rank equal to $|A|$. On the other hand, if the degree of $f$ (over $p\cdot A$) is at most $d$ then, by Lemma~\ref{lem-clpmodp}, the tensor $T$ has rank at most $p\cdot \cM_{\lfloor d/p \rfloor}(p,n)$. Since we assume that $|A| > p\cdot \cM_{\lfloor d/p \rfloor}(p,n)$ this cannot happen and so $\intdeg_p(pA) > d$. \end{proof} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{Acknowledgements} We thank Stijn Cambie for helpful comments on an earlier draft of this manuscript. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % You do not have to use the same format for your references, but % include everything in this file. Don't use natbib please. % If you use BibTeX to create a bibliography, copy the .bbl file into here. %\begin{thebibliography}{99} %%\providecommand{\natexlab}[1]{#1} %%\providecommand{\url}[1]{\texttt{#1}} %%\expandafter\ifx\csname urlstyle\endcsname\relax %% \providecommand{\doi}[1]{doi: #1}\else %% \providecommand{\doi}{doi: \begingroup \urlstyle{rm}\Url}\fi % %\bibitem[Babai and Frankl(1992)]{babai92book} %L~Babai and P~Frankl. %\newblock \emph{{Linear Algebra Methods in Combinatorics}}. %\newblock University of Chicago, 1992. % %\bibitem[{Blumer} et~al.(1989){Blumer}, {Ehrenfeucht}, {Haussler}, and % {Warmuth}]{blumer89VC} %A.~{Blumer}, A.~{Ehrenfeucht}, D.~{Haussler}, and M.~K. {Warmuth}. %\newblock {Learnability and the Vapnik-Chervonenkis dimension.} %\newblock \emph{{J. Assoc. Comput. Mach.}}, 36\penalty0 (4):\penalty0 929--965, % 1989. %\newblock ISSN 0004-5411. %\newblock \doi{10.1145/76359.76371}. % %\bibitem[Croot et~al.(2017)Croot, Lev, and Pach]{CLP17} %Ernie Croot, Vsevolod~F. Lev, and P\'eter~P\'al Pach. %\newblock Progression-free sets in {$\Bbb Z^n_4$} are exponentially small. %\newblock \emph{Ann. of Math. (2)}, 185\penalty0 (1):\penalty0 331--337, 2017. %\newblock ISSN 0003-486X. %\newblock \doi{10.4007/annals.2017.185.1.7}. %\newblock URL \url{https://doi.org/10.4007/annals.2017.185.1.7}. % %\bibitem[Dvir and Edelman(2017)]{DB17} %Zeev Dvir and Benjamin Edelman. %\newblock Matrix rigidity and the croot-lev-pach lemma. %\newblock Manuscript, 08 2017. % %\bibitem[Ellenberg and Gijswijt(2017)]{EG17} %Jordan~S. Ellenberg and Dion Gijswijt. %\newblock On large subsets of {$\Bbb F^n_q$} with no three-term arithmetic % progression. %\newblock \emph{Ann. of Math. (2)}, 185\penalty0 (1):\penalty0 339--343, 2017. %\newblock ISSN 0003-486X. %\newblock \doi{10.4007/annals.2017.185.1.8}. %\newblock URL \url{https://doi.org/10.4007/annals.2017.185.1.8}. % %\bibitem[Fox and Lov\'{a}sz(2017)]{Fox17} %Jacob Fox and L\'{a}szl\'{o}~Mikl\'{o}s Lov\'{a}sz. %\newblock A tight bound for green's arithmetic triangle removal lemma in vector % spaces. %\newblock In \emph{Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium % on Discrete Algorithms}, SODA '17, pages 1612--1617, Philadelphia, PA, USA, % 2017. Society for Industrial and Applied Mathematics. %\newblock URL \url{http://dl.acm.org/citation.cfm?id=3039686.3039792}. % %\bibitem[Green(2016)]{Green16} %Ben Green. %\newblock Sarkozy's theorem in function fields. %\newblock \emph{Quarterly Journal of Mathematics}, 68, 2016. % %\bibitem[Gurvits(1997)]{gurvits97linear} %Leonid Gurvits. %\newblock {Linear algebraic proofs of VC-dimension based inequalities}. %\newblock In \emph{Computational Learning Theory}, pages 238--250. Springer, % 1997. % %\bibitem[Moran and Rashtchian(2016)]{moran16shattered} %Shay Moran and Cyrus Rashtchian. %\newblock Shattered sets and the hilbert function. %\newblock In \emph{{MFCS}}, volume~58 of \emph{LIPIcs}, pages 70:1--70:14. % Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. % %\bibitem[Rassoul-Agha and Sepp{\"a}l{\"a}inen(2015)]{LDP15} %Firas Rassoul-Agha and Timo Sepp{\"a}l{\"a}inen. %\newblock \emph{A course on large deviations with an introduction to Gibbs % measures}. %\newblock American Mathematical Society, 05 2015. %\newblock ISBN 978-0-8218-7578-0. % %\bibitem[Remscrim(2016)]{Remscrim16} %Z.~Remscrim. %\newblock The hilbert function, algebraic extractors, and recursive fourier % sampling. %\newblock In \emph{2016 IEEE 57th Annual Symposium on Foundations of Computer % Science (FOCS)}, pages 197--208, Oct 2016. %\newblock \doi{10.1109/FOCS.2016.29}. % %\bibitem[{Sauer}(1972)]{sauer72density} %N.~{Sauer}. %\newblock {On the density of families of sets.} %\newblock \emph{{J. Comb. Theory, Ser. A}}, 13:\penalty0 145--147, 1972. %\newblock ISSN 0097-3165. %\newblock \doi{10.1016/0097-3165(72)90019-2}. % %\bibitem[Shelah(1972)]{shelah72comb} %Saharon Shelah. %\newblock A combinatorial problem; stability and order for models and theories % in infinitary languages. %\newblock \emph{Pacific J. Math.}, 41\penalty0 (1):\penalty0 247--261, 1972. %\newblock URL \url{https://projecteuclid.org:443/euclid.pjm/1102968432}. % %\bibitem[Smolensky(1997)]{smolensky97vc} %Roman Smolensky. %\newblock Well-known bound for the vc-dimension made easy. %\newblock \emph{Computational Complexity}, 6\penalty0 (4):\penalty0 299--300, % 1997. %\newblock \doi{10.1007/BF01270383}. %\newblock URL \url{http://dx.doi.org/10.1007/BF01270383}. % %\bibitem[Solymosi(2018)]{Soly18} %Jozsef Solymosi. %\newblock The sum of nonsingular matrices is often nonsingular. %\newblock \emph{Linear Algebra and its Applications}, 552, 01 2018. % %\bibitem[Tao(2016)]{Tao-capset} %T.~Tao. %\newblock {A symmetric formulation of the {C}root - {L}ev - {P}ach - % {E}llenberg - {G}ijswijt capset bound}. %\newblock % https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg, % 2016. % %\end{thebibliography} \begin{thebibliography}{99} \bibitem{babai92book} L.~Babai and P.~Frankl. \newblock \emph{{Linear Algebra Methods in Combinatorics}}. \newblock University of Chicago, 1992. \bibitem{blumer89VC} A.~{Blumer}, A.~{Ehrenfeucht}, D.~{Haussler}, and M.~K. {Warmuth}. \newblock {Learnability and the Vapnik-Chervonenkis dimension.} \newblock \emph{{J. Assoc. Comput. Mach.}}, 36\penalty0 (4):\penalty0 929--965, 1989. \newblock ISSN 0004-5411. \newblock \doi{10.1145/76359.76371}. \bibitem{CLP17} E.~Croot, V.~F. Lev, and P.~P.~Pach. \newblock Progression-free sets in {$\Bbb Z^n_4$} are exponentially small. \newblock \emph{Ann. of Math. (2)}, 185\penalty0 (1):\penalty0 331--337, 2017. \newblock ISSN 0003-486X. \newblock \doi{10.4007/annals.2017.185.1.7}. \newblock URL \url{https://doi.org/10.4007/annals.2017.185.1.7}. \bibitem{DB17} Z.~Dvir and B.~Edelman. \newblock Matrix rigidity and the croot-lev-pach lemma. \newblock Manuscript, 08 2017. \bibitem{EG17} J.~S. Ellenberg and D.~Gijswijt. \newblock On large subsets of {$\Bbb F^n_q$} with no three-term arithmetic progression. \newblock \emph{Ann. of Math. (2)}, 185\penalty0 (1):\penalty0 339--343, 2017. \newblock ISSN 0003-486X. \newblock \doi{10.4007/annals.2017.185.1.8}. \newblock URL \url{https://doi.org/10.4007/annals.2017.185.1.8}. \bibitem{Fox17} J.~Fox and L.~M.~Lov\'{a}sz. \newblock A tight bound for green's arithmetic triangle removal lemma in vector spaces. \newblock In \emph{Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms}, SODA '17, pages 1612--1617, Philadelphia, PA, USA, 2017. Society for Industrial and Applied Mathematics. \newblock URL \url{http://dl.acm.org/citation.cfm?id=3039686.3039792}. \bibitem{Green16} B.~Green. \newblock Sarkozy's theorem in function fields. \newblock \emph{Quarterly Journal of Mathematics}, 68, 2016. \bibitem{gurvits97linear} L.~Gurvits. \newblock {Linear algebraic proofs of VC-dimension based inequalities}. \newblock In \emph{Computational Learning Theory}, pages 238--250. Springer, 1997. \bibitem{moran16shattered} S.~Moran and C.~Rashtchian. \newblock Shattered sets and the hilbert function. \newblock In \emph{{MFCS}}, volume~58 of \emph{LIPIcs}, pages 70:1--70:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. \bibitem{LDP15} F.~Rassoul-Agha and T.~Sepp{\"a}l{\"a}inen. \newblock \emph{A course on large deviations with an introduction to Gibbs measures}. \newblock American Mathematical Society, 05 2015. \newblock ISBN 978-0-8218-7578-0. \bibitem{Remscrim16} Z.~Remscrim. \newblock The hilbert function, algebraic extractors, and recursive fourier sampling. \newblock In \emph{2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)}, pages 197--208, Oct 2016. \newblock \doi{10.1109/FOCS.2016.29}. \bibitem{sauer72density} N.~{Sauer}. \newblock {On the density of families of sets.} \newblock \emph{{J. Comb. Theory, Ser. A}}, 13:\penalty0 145--147, 1972. \newblock ISSN 0097-3165. \newblock \doi{10.1016/0097-3165(72)90019-2}. \bibitem{shelah72comb} S.~Shelah. \newblock A combinatorial problem; stability and order for models and theories in infinitary languages. \newblock \emph{Pacific J. Math.}, 41\penalty0 (1):\penalty0 247--261, 1972. \newblock URL \url{https://projecteuclid.org:443/euclid.pjm/1102968432}. \bibitem{smolensky97vc} R.~Smolensky. \newblock Well-known bound for the VC-dimension made easy. \newblock \emph{Computational Complexity}, 6\penalty0 (4):\penalty0 299--300, 1997. \newblock \doi{10.1007/BF01270383}. \newblock URL \url{http://dx.doi.org/10.1007/BF01270383}. \bibitem{Soly18} J.~Solymosi. \newblock The sum of nonsingular matrices is often nonsingular. \newblock \emph{Linear Algebra and its Applications}, 552, 01 2018. \bibitem{Tao-capset} T.~Tao. \newblock {A symmetric formulation of the {C}root - {L}ev - {P}ach - {E}llenberg - {G}ijswijt capset bound}. \newblock https://terrytao.wordpress.com/2016/05/18/a-symmetric-formulation-of-the-croot-lev-pach-ellenberg, 2016. \end{thebibliography} \end{document}