OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Section 1 (setting): real Fourier degree and the two linear sums: Real functions on the uniform sign cube and their Fourier-Walsh coefficients

Fourier degree and two linear sums.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The library fixes a common setting for real Fourier degree and linear Fourier sums.

The Definition

Definition 1. For a coordinate set II, the sign cube ΩI\Omega_I is the set of sign assignments to its coordinates in (1). ΩI={−1,1}I.\Omega_I=\{-1,1\}^{I}.(1)✦ The binary sign map σ:{0,1}→{−1,1}\sigma:\{0,1\}\to\{-1,1\} is the function in (2). σ(b)=(−1)b={1,b=0,−1,b=1.\sigma(b)=(-1)^b= \begin{cases} 1,&b=0,\\ -1,&b=1. \end{cases}(2)✦

For a finite set AA and a real function g:A→ℝg:A\to\mathbb R, the uniform average 𝔼Ag\mathbb E_A g is the number in (3), with 0−1=00^{-1}=0. 𝔼Ag=|A|−1∑a∈Ag(a).\mathbb E_A g=|A|^{-1}\sum_{a\in A}g(a).(3)✦ For a finite subset S⊆IS\subseteq I, the Walsh character χS:ΩI→ℝ\chi_S:\Omega_I\to\mathbb R is the coordinate product in (4). χS(x)=∏i∈Sxi(x∈ΩI).\chi_S(x)=\prod_{i\in S}x_i \qquad(x\in\Omega_I).(4)✦

Let II be finite and f:ΩI→ℝf:\Omega_I\to\mathbb R. For a finite coordinate set II and a real function f:ΩI→ℝf:\Omega_I\to\mathbb R, the real Fourier-Walsh coefficient fˆ(S)\widehat f(S) at S⊆IS\subseteq I is the uniform correlation in (5). fˆ(S)=𝔼ΩI(fχS).\widehat f(S)=\mathbb E_{\Omega_I}(f\chi_S).(5)✦ For a finite coordinate set II and a real function f:ΩI→ℝf:\Omega_I\to\mathbb R, the Fourier degree deg⁡f\deg f is the ordinary real multilinear degree in (6), with constants and the zero function assigned degree zero. deg⁡f=max⁡({|S|:S⊆I,fˆ(S)≠0}∪{0}).\deg f=\max\bigl(\{\,|S|:S\subseteq I,\ \widehat f(S)\ne0\,\}\cup\{0\}\bigr).(6)✦ Polynomial threshold degree and degree over a finite field are separate notions.

For any set XX, a Boolean-valued real function g:X→ℝg:X\to\mathbb R is a function satisfying (7). g(x)∈{−1,1}(x∈X).g(x)\in\{-1,1\}\qquad(x\in X).(7)✦ A nonconstant real function g:X→ℝg:X\to\mathbb R is a function having two points with different values, as in (8). ∃x,y∈X,g(x)≠g(y).\exists x,y\in X,\qquad g(x)\ne g(y).(8)✦

For f:ΩI→ℝf:\Omega_I\to\mathbb R with II finite, the signed singleton sum L(f)L(f) is the sum in (9). L(f)=∑i∈Ifˆ({i}).L(f)=\sum_{i\in I}\widehat f(\{i\}).(9)✦ For f:ΩI→ℝf:\Omega_I\to\mathbb R with II finite, the absolute singleton sum Labs(f)L_{\mathrm{abs}}(f), also called the level-one ℓ1\ell^1 mass, is the sum in (10). Labs(f)=∑i∈I|fˆ({i})|.L_{\mathrm{abs}}(f)=\sum_{i\in I}|\widehat f(\{i\})|.(10)✦

What Is Checked

The Fourier quantities are defined for arbitrary real functions on finite uniform sign cubes, while Boolean-valuedness and nonconstancy apply to real functions on any set.