Return to Answer

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we have two functions $f,g\in\mathbb F^A$ such that $$\sum_{a\in A} f(a)Q(a)=\sum_{a\in A} g(a)Q(a)=0 \tag{$\ast$} $$ for any polynomial $Q\in\mathbb F[x_1,\ldots,x_n]$ of degree $\deg Q\leqslant d$. Then $$ \sum_{a\in A,b\in A} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $2d+1$. (If $Q$ is a monomial, then our sum factorizes and one of factors is 0.)

Applying this with the polynomial $Q(x,y):=P(x-y)$, where $\deg P\leqslant 2d+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$, we get $$ 0=\sum_{a\in A,b\in A} f(a)g(b)P(a-b)=P(0)\cdot \sum_{a\in A} f(a)g(a). $$ Now if $P(0)\ne 0$, then $\sum_{a\in A} f(a)g(a)=0$ for any two functions $f,g\in\mathbb F^A$ . Then functions $f,g$ satisfying ($\ast$). This condition determines a linear subspace of $\mathbb F^A$ of dimension at least $|A|-\binom{n+d}d$ (or $|A|-\sum_{i\leqslant d} \binom{n}i$, if we consider only multilinear polynomials). We have thus shown that if $P(0,0)\ne 0$, then this is an isotropic subspace (any two vectors are mutually orthogonal.) The maximal dimension of an isotropic subspace is well-studied. It cannot exceed $|A|/2$ by obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension $1$.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we have two functions $f,g\in\mathbb F^A$ such that $$\sum_{a\in A} f(a)Q(a)=\sum_{a\in A} g(a)Q(a)=0 \tag{$\ast$} $$ for any polynomial $Q\in\mathbb F[x_1,\ldots,x_n]$ of degree $\deg Q\leqslant d$. Then $$ \sum_{a\in A,b\in A} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $2d+1$. (If $Q$ is a monomial, then our sum factorizes and one of factors is 0.)

Applying this with the polynomial $Q(x,y):=P(x-y)$, where $\deg P\leqslant 2d+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$, we get $$ 0=\sum_{a\in A,b\in A} f(a)g(b)P(a-b)=P(0)\cdot \sum_{a\in A} f(a)g(a). $$ Now if $P(0)\ne 0$, then $\sum_{a\in A} f(a)g(a)=0$ for any two functions $f,g\in\mathbb F^A$ . Then functions $f,g$ satisfying ($\ast$). This condition determines a linear subspace of $\mathbb F^A$ of dimension at least $|A|-\binom{n+d}d$ (or $|A|-\sum_{i\leqslant d} \binom{n}i$, if we consider only multilinear polynomials). We have thus shown that if $P(0,0)\ne 0$, then this is an isotropic subspace (any two vectors are mutually orthogonal.) The maximal dimension of an isotropic subspace is well-studied. It cannot exceed $|A|/2$ by obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension $1$.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we managed to find functions $f,g$ so that $\sum_{a\in A} f(a)W(a)=0$ if $\deg W\leqslant \alpha$, $\sum_{b\in B} g(b) W(b)=0$ if $\deg W\leqslant \beta$. Then we have $$ \sum_{a\in A,b\in A} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $\alpha+\beta+1$. Indeed, if $Q$ is monomial, then our sum factorizes and one of factors is 0.

Apply this for $A=B$ and a polynomial $Q(x,y)=P(x-y)$, where $\deg P\leqslant \alpha+\beta+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$. We get $$ 0=\sum_{a\in A,b\in A} f(a)g(b)P(a-b)=P(0)\cdot \sum f(a)g(a). $$ Now if $\sum f(a)g(a)\ne 0$, we conclude that $P(0)=0$. Assume for simplicity that $\alpha=\beta$. Then functions $f,g$ satisfying our condition are chosen in the same linear space of dimension at least $|A|-\binom{n+\alpha}\alpha$ (or $|A|-\sum_{i\leqslant \alpha} \binom{n}i$, if we consider only multilinear polynomials). If $P(0,0)\ne 0$, then this space is an isotropic subspace of $\mathbb{F}^{A}$ (any two vectors must be orthogonal.) Maximal dimension of isotropic subspace is well known subject and it always does not exceed $|A|/2$ be obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension 1.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we have two functions $f,g\in\mathbb F^A$ such that $$\sum_{a\in A} f(a)Q(a)=\sum_{a\in A} g(a)Q(a)=0 \tag{$\ast$} $$ for any polynomial $Q\in\mathbb F[x_1,\ldots,x_n]$ of degree $\deg Q\leqslant d$. Then $$ \sum_{a\in A,b\in A} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $2d+1$. (If $Q$ is a monomial, then our sum factorizes and one of factors is 0.)

Applying this with the polynomial $Q(x,y):=P(x-y)$, where $\deg P\leqslant 2d+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$, we get $$ 0=\sum_{a\in A,b\in A} f(a)g(b)P(a-b)=P(0)\cdot \sum_{a\in A} f(a)g(a). $$ Now if $P(0)\ne 0$, then $\sum_{a\in A} f(a)g(a)=0$ for any two functions $f,g\in\mathbb F^A$ . Then functions $f,g$ satisfying ($\ast$). This condition determines a linear subspace of $\mathbb F^A$ of dimension at least $|A|-\binom{n+d}d$ (or $|A|-\sum_{i\leqslant d} \binom{n}i$, if we consider only multilinear polynomials). We have thus shown that if $P(0,0)\ne 0$, then this is an isotropic subspace (any two vectors are mutually orthogonal.) The maximal dimension of an isotropic subspace is well-studied. It cannot exceed $|A|/2$ by obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension $1$.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we managed to find functions $f,g$ so that $\sum f(a)W(a)=0$ if $\deg W\leqslant \alpha$, $\sum g(a) W(a)=0$ if $\deg W\leqslant \beta$. Then we have $$ \sum_{a\in A,b\in B} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $\alpha+\beta+1$. Indeed, if $Q$ is monomial, then our sum factorizes and one of factors is 0.

Apply this for a polynomial $Q(x,y)=P(x-y)$, where $\deg P\leqslant \alpha+\beta+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$. We get $$ 0=\sum_{a\in A,b\in B} f(a)g(b)P(a-b)=P(0)\cdot \sum f(a)g(a). $$ Now if $\sum f(a)g(a)\ne 0$, we conclude that $P(0)=0$. Assume for simplicity that $\alpha=\beta$. Then functions $f,g$ satisfying our condition are chosen in the same linear space of dimension at least $|A|-\binom{n+\alpha}\alpha$ (or $|A|-\sum_{i\leqslant \alpha} \binom{n}i$, if we consider only multilinear polynomials). If $P(0,0)\ne 0$, then this space is an isotropic subspace of $\mathbb{F}^{A}$ (any two vectors must be orthogonal.) Maximal dimension of isotropic subspace is well known subject and it always does not exceed $|A|/2$ be obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension 1.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.

Here is a small comment to Seva's answer, which allows to get smaller bounds for some fields.

Assume that we managed to find functions $f,g$ so that $\sum_{a\in A} f(a)W(a)=0$ if $\deg W\leqslant \alpha$, $\sum_{b\in B} g(b) W(b)=0$ if $\deg W\leqslant \beta$. Then we have $$ \sum_{a\in A,b\in A} f(a)g(b)Q(a,b)=0 $$ for any polynomial $Q$ of degree at most $\alpha+\beta+1$. Indeed, if $Q$ is monomial, then our sum factorizes and one of factors is 0.

Apply this for $A=B$ and a polynomial $Q(x,y)=P(x-y)$, where $\deg P\leqslant \alpha+\beta+1$ and $P(a,b)=0$ for $a,b\in A$, $a\ne b$. We get $$ 0=\sum_{a\in A,b\in A} f(a)g(b)P(a-b)=P(0)\cdot \sum f(a)g(a). $$ Now if $\sum f(a)g(a)\ne 0$, we conclude that $P(0)=0$. Assume for simplicity that $\alpha=\beta$. Then functions $f,g$ satisfying our condition are chosen in the same linear space of dimension at least $|A|-\binom{n+\alpha}\alpha$ (or $|A|-\sum_{i\leqslant \alpha} \binom{n}i$, if we consider only multilinear polynomials). If $P(0,0)\ne 0$, then this space is an isotropic subspace of $\mathbb{F}^{A}$ (any two vectors must be orthogonal.) Maximal dimension of isotropic subspace is well known subject and it always does not exceed $|A|/2$ be obvious reasons (such a space is contained in its own orthogonal complement). For real field there is no isotropic subspace even of dimension 1.

See the answer by Robin Chapman to my old question here for references on isotropic subspaces.