Aaronson-Ambainis Conjecture

Aaronson-Ambainis Conjecture

Definitions and mathematical statement

For a multilinear polynomial $f:\{-1,1\}^n\to[0,1]$ of degree at most $d\ge1$, write \[ f(x)=\sum_{S\subseteq[n]}\widehat f(S)\prod_{i\in S}x_i. \] Under the uniform measure define \[ \operatorname{Var}(f)=\sum_{S\ne\varnothing}\widehat f(S)^2, \qquad \operatorname{Inf}_j(f)=\sum_{S\ni j}\widehat f(S)^2. \] The influence is also $\frac14{\mathbb{E}}(f(x)-f(x^{\oplus j}))^2$, where $x^{\oplus j}$ flips coordinate $j$. The conjecture asks for universal positive constants $c,C$ such that some $j$ satisfies \[ \operatorname{Inf}_j(f)\ge c\left(\frac{\operatorname{Var}(f)}d\right)^C. \] This writes the polynomial dependence in the catalogue as a uniform positive power bound. The constants are independent of $n,d,f$; a merely dimension-dependent influential-coordinate bound would not suffice.

Formulation and concept references: [S1].

Short English statement

Must a bounded low-degree polynomial with nonzero variance have some coordinate whose influence is polynomially large in that variance and inverse degree?

Research attempt

Scope, process, and first gap.

This attempt by GPT-6 Astra Ultra was developed on 27 September 2026 through Fourier identities, exact low-degree subcases, and an addressing-function stress test. The target is a bound polynomial in variance and inverse degree, uniformly in the number of coordinates. All influences use the normalization in the statement. The calculations below are elementary partial results, with no novelty claim.

The source [S1, Conjecture 1.3] concerns bounded real-valued polynomials and proves a result for random restrictions under specified conditions. A coordinate influential after restriction need not have the same influence before restriction. We do not remove that distinction. The first gap in the route examined here is controlling Fourier cancellation strongly enough to replace a coefficient-norm bound that can be exponential in degree by a polynomial bound on some coordinate influence.

The dimension-dependent estimate, with its exact weakness.

Put $V=\operatorname{Var}(f)$ and $I_j=\operatorname{Inf}_j(f)$. Summing the Fourier definition over coordinates gives \[ V\le\sum_j I_j =\sum_{S\ne\varnothing}|S|\widehat f(S)^2 \le dV. \tag{443.1} \] Thus $\max_j I_j\ge V/n$. This proves that some coordinate matters when $V>0$, but it has the forbidden dependence on $n$. The upper bound on the sum does not bound the number of nonzero terms in that sum. A low-degree polynomial can involve arbitrarily many variables.

Boundedness also gives $0\le V\le1/4$, because $\mathbb E f^2\le\mathbb E f$ and $\mathbb E f-(\mathbb E f)^2\le1/4$. If $V=0$, every influence is zero and the desired numerical inequality is trivial. The nontrivial issue is positive variance, not simply the presence of a formal high-degree coefficient.

A full proof in degree one.

Write $f(x)=a_0+\sum_i a_i x_i$. Independent choices of the signs attain the extreme values $a_0\pm L$, where $L=\sum_i|a_i|$. Since both lie in $[0,1]$, \[ L\le\min(a_0,1-a_0)\le\tfrac12. \] Let $M=\max_i|a_i|$. Then \[ V=\sum_i a_i^2\le M\sum_i|a_i|\le M/2, \] so \[ \max_i I_i=M^2\ge4V^2. \tag{443.2} \] This bound is independent of the dimension. The argument uses the ability to make all linear terms have the same sign at one input, rather than discarding the range condition.

It is sharp as a dependence on variance: for $f(x)=\tfrac12+\frac1{2n}\sum_i x_i$, one has $V=1/(4n)$ and $\max_i I_i=1/(4n^2)=4V^2$. The small variance in this example is essential; it is not a constant-variance counterexample with vanishing influence.

An extension to disjoint monomial supports.

Suppose \[ f(x)=a_0+\sum_{\nu=1}^r a_\nu\chi_{S_\nu}(x), \qquad S_\nu\ne\varnothing, \] and the sets $S_\nu$ are pairwise disjoint. The monomial signs can again be chosen independently: set all but one coordinate in each support to $1$, then choose the remaining coordinate to prescribe that monomial's sign. Consequently $\sum_\nu|a_\nu|\le1/2$.

Orthogonality gives $V=\sum_\nu a_\nu^2$, and any coordinate in $S_\nu$ has influence $a_\nu^2$. The preceding proof therefore gives $\max_iI_i\ge4V^2$ regardless of the sizes of the supports. Since $d\ge1$, this also implies the requested form with exponent two for this subclass. Overlapping supports invalidate the independent-sign step; that is the precise extra assumption used.

A general coefficient-norm lemma.

For an arbitrary expansion let \[ L=\sum_{S\ne\varnothing}|\widehat f(S)|. \] If $V>0$, choose a nonconstant coefficient of largest absolute value $M$. Since $V\le ML$, it satisfies $M\ge V/L$. Every coordinate in that coefficient's support has influence at least $M^2$, and hence \[ \max_i I_i\ge V^2/L^2. \tag{443.3} \] Thus a polynomial bound on this nonconstant Fourier $\ell^1$ norm would provide a sufficient route. Bounded range alone, however, does not give such a polynomial bound in degree. The next example proves that this particular sufficient condition is too strong.

An exact addressing-function countertest.

Take $k$ address bits $a\in\{-1,1\}^k$ and $2^k$ data bits $y_\omega$, indexed by $\omega\in\{-1,1\}^k$. Define \[ f(a,y)=\frac{1+y_a}{2} =\frac12+\frac12\sum_\omega y_\omega \prod_{j=1}^k\frac{1+\omega_j a_j}{2}. \tag{443.4} \] This is a Boolean-valued member of the required range, with degree $k+1$ and variance $1/4$. Expanding the products produces $2^{2k}$ distinct nonconstant monomials, all of coefficient magnitude $2^{-k-1}$. Their supports are distinct because each carries its own data variable. Therefore \[ L=2^{k-1}. \] The coefficient-norm route $443.3$ becomes exponentially weak in the degree, despite the variance staying fixed.

The example itself has large influences. Flipping one address bit selects a different independent data bit. The two selected data values differ with probability $1/2$, so the normalized influence is $(1/4)(1/2)=1/8$. Flipping a specified data bit changes $f$ exactly when it is addressed, with probability $2^{-k}$, giving influence $2^{-k-2}$. Thus the address bits satisfy the conjectured type of conclusion. This countertest disproves a proposed auxiliary polynomial $\ell^1$ bound, not the Aaronson--Ambainis conjecture.

An exponential bound for Boolean-valued polynomials.

There is a useful elementary bound for the narrower range $\{0,1\}$. A nonzero multilinear polynomial of degree at most $r$ on a Boolean cube is nonzero on at least a $2^{-r}$ fraction of inputs. Prove this by induction on $r$: a nonconstant polynomial can be written $x_iq+r_0$ with $q\ne0$ of degree at most $r-1$. Whenever $q$ is nonzero, at least one of the two choices of $x_i$ makes the original polynomial nonzero. The constant case begins the induction.

For a relevant coordinate define \[ D_if(x)=\frac{f(x)-f(x^{\oplus i})}{2}. \] After removing the harmless factor $x_i$, this is a nonzero polynomial in the other variables of degree at most $d-1$. If $f$ is $\{0,1\}$-valued, its nonzero values have absolute value $1/2$. Hence \[ I_i=\mathbb E(D_if)^2\ge 2^{-d-1}. \] This proves a degree-dependent influence lower bound for relevant variables in the Boolean-valued subclass, but the exponential dependence is insufficient for the conjecture. For a merely $[0,1]$-valued polynomial, nonzero derivatives can be arbitrarily small, so the discrete-value step cannot be reused.

Verification and outcome.

The checks expand small addressing functions exactly, verify their variance and both types of influence, and check the degree-one equality examples. The support lemma explicitly concerns nonzero functions on the cube, using their unique multilinear representation. No random restriction is treated as preserving variance or influence without calculation.

UNRESOLVED. Dimension-free quadratic bounds are proved for linear polynomials and disjoint-support monomial sums. A general coefficient-norm estimate and an exponential Boolean-valued estimate are also proved. The first remaining gap is a dimension-free polynomial influence argument for overlapping bounded polynomials that survives the cancellations exhibited by addressing functions.

Sources

• S1 Sreejata Kishor Bhattacharya, "Aaronson-Ambainis Conjecture Is True For Random Restrictions," ECCC TR24-035 $2024$; also ITCS 2025, LIPIcs vol. 325. https://eccc.weizmann.ac.il/report/2024/035/download/. Formulation source.