Hadamard linearity constraint system

Let $n\ge 0$ and let $f:{\mathbb{F}}_2^n\to {\mathbb{F}}_2$ be a fixed table, in the conventions of The BLR linearity test over F_2. The Hadamard linearity constraint system ${\mathrm{Lin}}_n(f)$ is the constraint system of arity at most $3$ over the alphabet ${\mathbb{F}}_2$ of Assignment tester and rejection ratio whose variables are the table coordinates $z\in {\mathbb{F}}_2^n$ — one variable per cube point, so $V={\mathbb{F}}_2^n$ — and whose constraint list contains, once for each ordered pair $(x,y)\in {\mathbb{F}}_2^n\times {\mathbb{F}}_2^n$, the ternary constraint with variable tuple $(x,y,x+y)$ and relation $R_{\mathrm{l}\mathrm{i}\mathrm{n}}:=\{(a,b,c)\in {\mathbb{F}}_2^3:a+b=c\},$ the addition being modulo two. The list is a list, so constraints belonging to different pairs are counted separately even when they coincide as tuples.

Since $x,y$ range over the whole cube, the variable tuple of a constraint may repeat coordinates — for instance $(0,0,0)$ for the pair $(0,0)$, and $(x,x,0)$ for $(x,x)$ — and the satisfaction rule of a constraint system is the substitution rule: the tuple $(x,y,x+y)$ is satisfied by a labeling $\sigma :{\mathbb{F}}_2^n\to {\mathbb{F}}_2$ exactly when $\sigma (x)+\sigma (y)=\sigma (x+y)$, coinciding coordinates being read as the single symbol assigned to them. The same substitution covers the degenerate cases: the pair $(0,0)$ forces $\sigma (0)=0$, and for $n=0$ the cube has one point, the list has the single constraint with tuple $(0,0,0)$, and the system is satisfied exactly by the table $f(0)=0$.

Value and rejection probability. For a labeling $\sigma$ of ${\mathrm{Lin}}_n(f)$ — that is, an arbitrary table $\sigma :{\mathbb{F}}_2^n\to {\mathbb{F}}_2$ — the fraction ${\mathrm{val}}_{\sigma }$ counts the satisfied constraints among the $4^n$ listed pairs, and ${\mathrm{UNSAT}}_{\sigma }=1-{\mathrm{val}}_{\sigma }$. For the fixed table $f$ we write ${\epsilon }_{\mathrm{l}\mathrm{i}\mathrm{n}}(f):=1-{\mathrm{val}}_f({\mathrm{Lin}}_n(f))=\frac{\mathrm{\#}\{(x,y):f(x)+f(y)\mathrm{\ne }f(x+y)\}}{4^n},$ the rejection probability of the linearity system, which is exactly the BLR rejection probability of $f$ in the sense of The BLR linearity test over F_2: the pair $(x,y)$ is drawn uniformly in the test and the listed constraint at that pair is violated precisely when the test rejects. In particular a uniformly random constraint of the system involves the three coordinates $x,y,x+y$ and is checked with three table queries and $2n$ random bits.

Perfect completeness. Every linear table passes. If $f={\mathrm{\ell }}_u$ for some $u\in {\mathbb{F}}_2^n$, then for all $x,y$ the distributivity of the dot product over addition in ${\mathbb{F}}_2$ gives ${\mathrm{\ell }}_u(x)+{\mathrm{\ell }}_u(y)=u\cdot x+u\cdot y=u\cdot (x+y)={\mathrm{\ell }}_u(x+y)$, so every constraint of the system is satisfied and ${\epsilon }_{\mathrm{l}\mathrm{i}\mathrm{n}}({\mathrm{\ell }}_u)=0$. The system is explicit: its $4^n$ constraint tuples and its single fixed relation table $R_{\mathrm{l}\mathrm{i}\mathrm{n}}$ are enumerated by the displayed rule, and its size is determined by $n$ alone.

• One constraint per test, not one per violation pattern. The system records multiplicity: the pairs $(x,y)$ and $(y,x)$ give two constraints, and a pair with $x=y$ still gives one constraint. This is what makes ${\epsilon }_{\mathrm{l}\mathrm{i}\mathrm{n}}(f)$ equal — not merely comparable — to the rejection probability of the sampled BLR test, and it is the convention used by the exponential-base tester of An exponential-size constant-query base assignment tester, where every random choice of the verifier is materialized as one constraint.
• Relation to the proximity definition. The system constrains table coordinates, not inputs of a circuit: in the language of Assignment tester and rejection ratio the whole cube of table positions is the auxiliary part of the variable set, and the rejection probability is the quantity the soundness clause controls. The distance of a table from the linear tables is a property of the labeling of these coordinates, and BLR rejection is proportional to distance from linearity is the statement that the violated fraction is at least that distance.
• No random sampling is part of the definition. Sampling the pair $(x,y)$ is a way of estimating the value of an explicit, fully listed system; the system itself is deterministic and independent of any randomness, and it is produced by enumerating the $4^n$ pairs, which is polynomial in the size of the listing but exponential in $n$ as a description of $f$ requires.