PaperlayerView exact revision on arXiv

Source-linked AI summary

Logarithmic asymptotics for polynomial threshold functions

Martin Anthony

arXiv:2610.34378v1cs.DMcs.ITmath.COmath.IT

TL;DR

The paper asks whether the logarithm of the number of polynomial threshold functions attains the classical arrangement bound as degree grows. It derives degree-range estimates for the logarithmic gap and proves logarithmic equivalence for every degree, while leaving the stronger count-level question unresolved.

  • Problem

    The paper asks whether the logarithm of the polynomial-threshold count attains the classical hyperplane-arrangement upper bound as degree grows.

    Source: §1.1 · p. 1

  • Method

    It derives estimates across degree ranges for the logarithmic gap, including a product bound whose factors are approximated by log2(N/m).

    Source: §4.4 · p. 15, §6 · p. 27

  • Results

    Theorem A proves logarithmic equivalence to the arrangement bound for every degree; sharper estimates include an additive O(n^2) gap for 2 ≤ d ≤ 10^-4n and relative error O(log n/n) when 0 < n/2 − d = O(√n).

    Source: §6 · p. 27

  • Takeaways & Limitations

    The logarithmic asymptotic is established below the central degree, completing the all-degree logarithmic form of the enumeration conjecture.

    Source: §6 · p. 27

    The logarithmic equivalence allows a multiplicative discrepancy that may still be large, so it does not resolve whether T_n,d ∼ Q_n,d for every 2 ≤ d < n/2.

    Source: §6 · p. 28

Abstract

from arXiv · show

We count Boolean functions represented as the sign of a real polynomial of bounded degree on the $n$-dimensional cube. We prove that the logarithm of their number is asymptotic to that of the classical hyperplane-arrangement upper bound, uniformly over all degrees, with relative error $O((\log n)^2/n)$. We also obtain sharper additive and relative error estimates in particular degree ranges, including an additive error $O(n^2)$ between the logarithms throughout a small linear degree range and improved bounds just below the central degree. The proof combines probabilistic estimates for Reed--Muller codes with a deletion argument for sets of evaluation vectors, an entropy count, and a sharp-threshold estimate for expected rank deficiency.

1 Introduction

The paper asks whether polynomial-threshold counts attain the classical hyperplane-arrangement upper bound logarithmically as degree grows. It proves logarithmic equivalence for every degree and gives sharper estimates in particular degree ranges.

1.1 Definitions and main results

  • The classical arrangement bound gives T_n,d ≤ Q_n,d by identifying threshold functions with chambers of a central hyperplane arrangement.Source: §1.1 · p. 1
  • Theorem A establishes the conjectured logarithmic equivalence between T_n,d and Q_n,d for every degree, with a uniform rate.Source: §1.1 · p. 2
  • For 2 ≤ d ≤ 10^-4n, the logarithmic gap is at most (n + 1) log2(N/m_n,d) + C, and the additive error is O(n^2).Source: §1.1 · p. 2
  • Theorem C gives relative error O(1/n) when the degree stays a fixed proportion below n/2.Source: §1.1 · p. 3
  • Theorem D gives relative error O(log n/n) when 0 < n/2 − d = O(√n), with further estimates when n/2 − d = o(n).Source: §1.1 · p. 3

1.2 Related work and proof strategy

  • The proofs turn probabilistic estimates into lower bounds by counting; B sharpens a first-moment argument, while C and D use random-point recovery estimates and expected nullity.Source: §1.2 · p. 4

2 Deduction of the all-degree theorem

The all-degree theorem is deduced by combining estimates across degree ranges. The proof treats degree one and the ranges below and above the central degree separately.

2 Deduction of the all-degree theorem

  • The degree-one case uses the quantitative estimate of Kahn, Komlós and Szemerédi to obtain E_n,1 = O(1/n).Source: §2 · pp. 4–5
  • For 2 ≤ d below n/2, the proof uses Theorem C up to a moving cutoff and Theorem D(ii) nearer n/2.Source: §2 · p. 5
  • For d ≥ ⌈n/2⌉, Theorem D(i) is applied just below the central degree, then degree monotonicity extends the bound to the upper range.Source: §2 · p. 6
  • Combining the degree-one estimate with bounds in three degree ranges yields the asserted uniform logarithmic equivalence.Source: §2 · p. 6

3 Evaluation vectors and counting

The section links polynomial evaluations to a binary evaluation matrix, then uses sets whose spans identify them to count hyperplane intersections. A deletion argument converts independent sets into such sets when needed.

3.1 The evaluation matrix over two fields

  • A single 0–1 evaluation matrix represents real polynomial evaluations and binary polynomial functions, with rank and span interpreted over the specified field.Its columns are indexed by cube vertices and rows by monomials of degree at most d; binary full row rank also implies real full row rank.Source: §3.1 · pp. 6–7

3.2 Sets that determine their spans

  • A good set has independent evaluation columns and no outside column in their binary span, so distinct good sets yield distinct hyperplane intersections and lower-bound the chamber count.The expected number of outside vertices that violate the condition for a random k-set is (N − k)q_{k+1}.Source: §3.2 · pp. 7–8

3.3 From independent sets to good sets

  • The deletion lemma turns an independent set into a good set by deleting at most ℓ columns that meet every representation of an extra column in its span.For the evaluation matrix with d < n, every dependent set has at least 2d+1 columns, supplying the lower bound used in the deletion argument.Source: §3.3 · pp. 8–9

4 Counts for small degrees

For small degrees, the proof bounds dependence among sampled evaluation columns using Reed–Muller codeword weights and bias, then counts good sets. The resulting logarithmic gap from the hyperplane-arrangement upper bound is O(n^2) uniformly in the stated degree range.

4.1 Codewords, weights and bias

  • Reed–Muller codewords are binary polynomial evaluation vectors, and their relative weight is the fraction of nonzero entries; bias expresses the corresponding imbalance between zeros and ones.Complementing a codeword reverses its bias, giving a symmetric bias distribution for a uniformly chosen codeword.Source: §4.1 · p. 10

4.2 The first moment and repeated vertices

  • The first-moment method bounds dependence for samples drawn with replacement by relating expected rank deficiency to the number of codewords vanishing on the sampled vertices.The proof uses E_f B_f^2 = 1/N and separates codewords by absolute bias; repeated-vertex samples are then subtracted to obtain a bound for distinct vertices.Source: §4.2 · pp. 10–12

4.3 The contribution of larger biases

  • Large-bias codewords require sufficiently small probability to offset their larger contribution to the weighted expectation; the proof bounds this contribution using Reed–Muller weight estimates.The stated estimates apply uniformly for 2 ≤ d ≤ 10^-4n and 1 ≤ r ≤ m.Source: §4.3 · pp. 12–13

4.4 Completion of the proof of Theorem B

  • The proof counts good evaluation-column sets and compares their number with the arrangement upper bound to obtain the logarithmic error estimates.The small-linear-degree restriction enters through the weighted bias estimates; for larger degrees, the paper uses coding estimates and a deletion argument.Source: §4.4 · pp. 14–16
  • 0 ≤ log2 Qn,d − log2 Tn,d ≤ (n + 1) log2(N/m) + O(1) = O(n^2) throughout 2 ≤ d ≤ 10^-4n.The proof also bounds the relative error by En,d ≤ Cn/m.Source: §4.4 · pp. 14–15

5 The intermediate and near-central degrees

For degrees below the central degree, the paper uses random evaluation matrices and counting arguments to bound the number of polynomial threshold functions. The resulting estimates give quantitative control on the logarithmic gap, with a relative bound that improves as the degree proportion stays farther below one half.

5.1 A quantitative bound below the central degree

  • For n^-1/3 ≤ ε < 1/2 and d ≤ (1/2 − ε)n, the random evaluation matrix has full row rank with probability tending to one under the stated growth condition.The condition is m2^-d/n^4 → ∞; the construction selects cube vertices independently with probability q.Source: §5.1 · p. 16
  • For degrees at least cn and at most (1/2 − ε)n, the same random-selection construction can make the full-rank failure probability at most any fixed ζ > 0 for sufficiently large n.This assertion is stated for every fixed c > 0 and ζ > 0.Source: §5.1 · p. 16
  • The logarithmic relative error satisfies En,d ≤ K ln 2 ln(e/ε)/(nε^2), while the additive error is bounded by a constant times m ln(e/ε).The proof first obtains independent sets from the full-rank estimate, then applies the deletion lemma to bound Tn,d.Source: §5.1 · pp. 16–18

5.2 Degrees just below the central degree

For degrees just below the central degree, the section relates the parameter a to the entropy expression and characterizes when a=o(n). It uses entropy counts and rank estimates to bound the logarithmic counting error and identify conditions for its vanishing.

5.2 Degrees just below the central degree

  • a lies between n ln 2(1−H2(d/n)) and that quantity plus ln(n+1), and a=o(n) iff n/2−d=o(n).Source: §5.2 · p. 18

5.2.1 An entropy count of independent sets

  • The entropy count bounds independent-set counts by encoding a random sampled set as a greedy independent basis and its remainder.The basis has at most I(B) possible values, while the remainder's entropy is bounded using its expected size and the concavity of binary entropy.Source: §5.2.1 · p. 19

5.2.2 Estimates for Theorem D

  • The quantity Λ satisfies 1+ln 2 ≤ Λ ≤ m(a+1)ln 2, and the error in the entropy bound is exponentially small relative to Λ when a/n≤δ0.Source: §5.2.2 · pp. 20–21

5.2.3 Rank of a random set of columns

  • When a≤δ0n, the expected nullity at sampling probability α=m/N is at most CIma/n.The proof expresses rank and nullity through integrals of the probability that a column lies in the span of sampled columns, then bounds those integrals using a sharp-threshold inequality.Source: §5.2.3 · pp. 22–24

5.2.4 Proof of Theorem D(i)

  • For Theorem D(i), sampling columns independently with probability α gives E|U|=m, and the nullity estimate feeds the entropy count used for the relative-error comparison with log2 Qn,d.Source: §5.2.4 · pp. 24–25
  • 0 ≤ E_{n,d} ≤ C(a + ln(n/a))/n, and E_{n,d} → 0 when n/2 − d = o(n).In this regime, log2 Q_{n,d} ∼ Λ, so the bound yields the stated asymptotic comparison for the logarithms.Source: §5.2.4 · p. 26

5.2.5 Sampling more columns for Theorem D(ii)

  • ρ ≤ C0(a/n)e^(−µnη/a) ≤ η when a ≤ δ0n and C0a/n ≤ η ≤ 1/10.With independent vertex sampling probability q = (1 + η)α, the selected matrix has expected rank (1 − ρ)m; the lemma applies for sufficiently large n and 1 ≤ d < n/2.Source: §5.2.5 · p. 26

5.2.6 Consequences of Theorem D

  • When a = Θ((ln n)^2), Theorem D(ii) gives E_{n,d} = O(ln n ln ln n/n), versus O((ln n)^2/n) from part (i).When a = Θ(ln n), part (i) is sharper.Source: §5.2.6 · p. 27
  • For d = ⌊n/2 − n^3/4⌋, a ∼ 2√n and part (i) gives E_{n,d} = O(n^−1/2).The passage introduces this degree to illustrate the improvement from part (ii), but does not provide its bound in the supplied text.Source: §5.2.6 · p. 27
  • Theorem D gives explicit bounds when α → 0 and a = o(n), while for n/2 − d = O(√n), Kudekar et al. [15, Theorem 27] give log2 T_{n,d} ∼ NH2(α) without a rate.For odd n, Theorem D includes the lower central degree ⌊n/2⌋; the upper central degree ⌈n/2⌉ is covered by the author’s stronger centrality theorem [4, Theorem 1].Source: §5.2.6 · p. 27

6 Conclusions and open questions

The paper establishes logarithmic asymptotics for every degree, with uniform relative error O((log n)^2/n), and sharper estimates in several degree ranges. The conclusions leave open the full enumeration conjecture and sharper error rates.

6 Conclusions and open questions

  • Theorem A gives log2 Tn,d ∼ log2 Qn,d for every degree sequence, with relative error O((log n)^2/n) uniformly over all degrees.The results complete the logarithmic asymptotic below the central degree.Source: §6 · p. 27
  • Theorem B gives additive gap O(n^2) for 2 ≤ d ≤ 10^-4n; Theorem C gives relative error O(1/n) for 2 ≤ d ≤ (1/2 − ε)n.Theorem D gives relative error O(log n/n) when 0 < n/2 − d = O(√n), with estimates throughout n/2 − d = o(n).Source: §6 · p. 27
  • The logarithmic equivalence does not resolve whether Tn,d ∼ Qn,d for every sequence 2 ≤ d < n/2, because a large multiplicative discrepancy remains possible.Resolving this would establish the full enumeration conjecture together with known results at degree one and at or above ⌈n/2⌉.Source: §6 · p. 28
  • The paper leaves open how far the additive O(n^2) estimate extends beyond the small linear degree range and whether its order can be improved there.The constant 10^-4 is a convenient choice for the weight estimates; the proof does not indicate a transition at that degree.Source: §6 · p. 28
  • The best relative-error rate remains open; the estimates do not determine the best rate throughout n/2 − d = o(n).A logarithmic product is maximised near a = √n, corresponding to n/2 − d of order n^3/4, but this does not show the actual error is largest there.Source: §6 · p. 28
  • For growing degrees d ≤ 10^-4n, independence of mn,d uniformly sampled evaluation vectors with probability tending to one remains an open question.The argument uses order n fewer vectors than the dimension; full-sample independence would be stronger, and an additional argument would still be needed for a sharper enumeration bound.Source: §6 · p. 28

A.1 Verification of the weight and bias estimates

The appendix verifies estimates used for the small linear degree range. Under 2 ≤ d ≤ 10^-4n, its bounds establish the stated weight estimate and the resulting uniform inequality.

A.1 Verification of the weight and bias estimates

  • The verification establishes the bound for 2 ≤ j ≤ d, while the minimum-weight bound gives W(2^-j) = 1 for j > d.The argument uses the uniform comparison nd^3 = o(m2^-d).Source: §A.1 · p. 29
  • The cited Sberlo–Shpilka bound applies for 1 ≤ ℓ ≤ L because t = 3ℓ + 3 < n/2 for sufficiently large n and d < n − t.Here L < 0.005n and d ≤ 10^-4n.Source: §A.1 · pp. 29–30
  • For all sufficiently large n, the verification gives 1 + nt ≤ (3/40)m e^-24γℓ uniformly over the stated ranges.It combines the weight bound and estimates including e^-24γℓ ≥ 2^-d and nt = o(m2^-d).Source: §A.1 · p. 30

A.2 Full rank for a random evaluation matrix

This section bounds the probability that a randomly selected evaluation matrix fails to have full row rank. The bound tends to zero under a stated dimension-to-degree condition, and uniformly when the degree is at least a fixed positive fraction of n.

A.2 Full rank for a random evaluation matrix

  • Failure of full row rank is equivalent to a nonzero Reed–Muller codeword vanishing at every selected vertex.For a word of relative weight w, the probability it vanishes on the sample is determined by excluding all Nw vertices where it is nonzero.Source: §A.2 · p. 31
  • If m2^-d/n^4 → ∞, the failure probability bound tends to zero for the stated degree sequences.The union bound groups nonzero Reed–Muller codeword weights into intervals; the low-weight contribution is controlled using the weight estimate.Source: §A.2 · pp. 31–32
  • For each fixed c > 0, when cn ≤ d the failure probability tends to zero uniformly over the stated parameters.The bound depends only on n and c.Source: §A.2 · p. 32

B Proof of the integral bounds

The section applies a sharp-threshold inequality to the probability that a fixed evaluation-matrix column lies in the span of the other selected columns. Integrating the resulting derivative bound yields estimates used for expected nullity.

B Proof of the integral bounds

  • The sharp-threshold inequality gives u′(t) ≥ c0 ln K σ2 ln(e/σ2)u(t)(1 − u(t)) for an increasing, non-constant event invariant under coordinate permutations.Here σ2 = 4t(1 − t); the application takes the event that a fixed column lies in the span of the other selected columns.Source: B Proof of the integral bounds · p. 32
  • For the fixed-column span event, affine maps over F2 fixing v act transitively on V \ {v}, supporting the symmetry condition in the inequality.The event is non-constant, with h(0) = 0 and h(1) = 1.Source: B Proof of the integral bounds · pp. 32–33
  • The derivative bound is specialized to h(t), yielding h′(t)/(h(t)(1 − h(t))) ≥ κ t ln(e/t), with κ = c2n.The section integrates this inequality to bound h(t) for 0 < t ≤ p and obtain (27) when κ > 1 and h(p) ≤ 1/2.Source: B Proof of the integral bounds · p. 33
  • Multiplying the integral of p(1 − h(t)) over t by N gives m − F(p), which is used to bound expected nullity.The proof bounds 1 − h(t) for t ≥ p by integrating the derivative inequality and then bounds the integral.Source: B Proof of the integral bounds · pp. 33–34

C Proof of Theorem D(ii)

The proof of Theorem D(ii) controls expected rank deficiency by sampling slightly more columns than the mean rank, then bounds the resulting entropy terms. A sharp-threshold estimate supplies the rank-deficiency control for the chosen sampling probability.

Proof of Theorem D(ii)

  • Choosing q = (1 + η)α gives an expected (1 + η)m selected columns, with η the proportional oversampling amount.The proof chooses η so Lemma 10 ensures ρ ≤ η.Source: C Proof of Theorem D(ii) · pp. 34–36
  • 1 − h(q) over h(q) is at most exp(−μηn/a), giving the rank-deficiency bound used in the proof.The proof integrates from the unique θ with h(θ) = 1/2 to q = (1 + η)α.Source: C Proof of Theorem D(ii) · pp. 34–35
  • The entropy comparison cancels the leading terms from the additional ηm columns; the remaining logarithmic terms reduce ηαa/ln 2 by at most 2αη.The proof applies this comparison for η ≤ 1/10.Source: C Proof of Theorem D(ii) · pp. 35–36
  • The resulting relative-error bound has terms cn {C0 + B ln(a + 2) ln(n/a)} and O(e−c′n).The exponentially small remainder, divided by log2 Qn,d, is O(e−c′n).Source: C Proof of Theorem D(ii) · pp. 36–37

Declaration of generative AI use

The author declares that Anthropic’s Claude and OpenAI’s ChatGPT assisted with literature research, mathematical checking, and revisions to the proofs and exposition.

Declaration of generative AI use

  • Claude and ChatGPT assisted with literature research, mathematical checking, and revisions; the author takes full responsibility for the paper.The declaration names Anthropic’s Claude and OpenAI’s ChatGPT.Source: Declaration of generative AI use · p. 37
Loading 2610.34378v1…