Polynomial compatibility on the Boolean cube from disjoint-support separators
Two low-degree polynomials can vanish at many vertices of a Boolean cube. This note gives an explicit condition ensuring that there is a vertex where both are nonzero: no individual coordinate may account for too much of either polynomial’s full squared norm. The argument is a credited deduction from established decision-tree and covariance results.
Read the manuscript
Open the original PDF · Download PDF · BibTeX · Zenodo record and DOI
The original PDF is reproduced unchanged. If the embedded reader is unavailable, use the open or download link. Its printed date is 17 October 2026; it prints no numeric version. Version 1.0.0 belongs to the Zenodo metadata.
Original abstract
We give an explicit affirmative answer to the two-polynomial question posed by Austrin in Oberwolfach Report 9/2025. Two nonzero real multilinear polynomials of degree at most d on the uniform Boolean cube have a common nonzero vertex whenever every relative coordinate influence is at most 1/(4096d⁸). In fact, disjoint supports force a relative influence at least 1/(1024d⁸). The result is a deduction from the disjoint-support separator of Li–Li–Li–Liu and the covariance inequality of O’Donnell–Saks–Schramm–Servedio, combined with a square-density estimate. We supply the complete deduction and an explicit separator constant. No novelty or first-priority claim is made for this consequence.
The precise guarantee
Let n, d ≥ 1 be integers. Let f and g be nonzero real multilinear polynomials on the uniform sign cube {−1, 1}n, each of degree at most d. The coordinates are independent fair signs.
For the multilinear expansion a(x) = ∑S ⊆ [n] â(S) ∏i ∈ S xi, define
‖a‖22 = E[a(X)2] = ∑S â(S)2,
RelInfi(a) = (∑S ∋ i â(S)2) / ‖a‖22.
The denominator includes the constant Fourier coefficient. It is the full L2 norm, not the variance. Set δ = maxi max{RelInfi(f), RelInfi(g)}.
Necessary for disjoint supports: if f(x)g(x) = 0 at every vertex, then δ ≥ 1/(1024d8).
Sufficient for compatibility: if every relative coordinate influence of both polynomials is at most 1/(4096d8), then some vertex satisfies f(x)g(x) ≠ 0. Both polynomial values are nonzero there; this is not a common-root assertion.
The supports need not cover the cube: arbitrary common zeros are allowed. Nonzero constants and n < d cause no exception. The zero polynomial is excluded because its relative influence has a zero denominator. Neither the exponent nor the constants are asserted to be optimal.
Why the bound follows
Assume the two supports are disjoint. The prior separator of Li, Li, Li and Liu, Lemma 3.5, supplies a total deterministic decision tree whose output h is 1 on the support of f and 0 on the support of g. Common-zero vertices receive labels too. The note extracts the depth bound T ≤ 16d4 using the classical Markov/Bernoulli argument presented by Kothari and coauthors. Queries do not repeat along a branch.
Replace each polynomial by its normalized squared density: u = f2/‖f‖22 and v = g2/‖g‖22. Both have expectation 1, while hu = u and hv = 0. Hence |Cov(h, u)| + |Cov(h, v)| = 1.
The real covariance inequality of O’Donnell, Saks, Schramm and Servedio, §3.3, Eq. (6) gives |Cov(h, w)| ≤ ½ ∑i ri Ai(w), where ri is the probability of querying coordinate i, and Ai(w) = E|w(X) − w(X(i))|. Here X(i) independently resamples that coordinate, leaving it unchanged with probability one-half. The inequality permits adaptive queries and variable branch lengths; w need not be computed by the tree.
Writing a = b + xic and applying Cauchy–Schwarz gives the square-density estimate Ai(a2/‖a‖22) ≤ 2√(ρi(1 − ρi)) ≤ 2√ρi, with ρi = RelInfi(a). Combining these statements and ∑i ri ≤ T yields
1 ≤ 2T√δ ≤ 32d4√δ.
Squaring gives the necessary 1/(1024d8) bound. At δ ≤ 1/(4096d8), the last expression is at most ½, a contradiction. The written proof treats the total tree and adaptive resampling directly.
Question, credit and scope
The target is Per Austrin’s two-polynomial question in Oberwolfach Report 9/2025, printed page 445. The note supplies the explicit application, square-density conversion and extracted separator constant. The separator, real covariance inequality and Markov/Bernoulli method are prior inputs. No novelty or first-priority claim is made for this consequence.
The earlier sufficient threshold from the CRYPTO 2022 work is strict: δ < 2−d/d. The non-strict endpoint printed in the workshop report fails already at d = 1 for f = 1 + x1 and g = 1 − x1, each with relative influence ½. The present inclusive 1/(4096d8) threshold has slack.
This theorem concerns exactly two real multilinear polynomials on the uniform Boolean cube. It does not settle the general distribution formulations in the CRYPTO paper, other groups or measures, or approximate-support variants. The proof gives no polynomial-runtime procedure for finding the vertex.
Historical comparison remains bounded by the versions inspected. The original note records that the full ePrint 2022/218 and full 2023/570 follow-up were outside its accessible full-body set; the official CRYPTO 2022 conference version was treated separately. This does not establish equivalence of editions, exhaustive coverage, firstness or the current global literature status.
Original files and citation
The two original assets are offered in the record’s order:
- Source and verification archive (ZIP, 315,765 bytes) · Zenodo original ZIP
- Manuscript (PDF, 67,089 bytes) · Zenodo original PDF
Kriebel, Alec. Polynomial compatibility on the Boolean cube from disjoint-support separators. 17 October 2026. Zenodo, version 1.0.0. doi:10.5281/zenodo.23443301. Download BibTeX.
Original authored paper, code and analysis are licensed under Creative Commons Attribution 4.0 International. Third-party works retain their own rights and are not relicensed; third-party source bodies are excluded from the archive.
References
- P. Austrin, “Zeros of Low-Degree, Low-Influence Polynomials on the Boolean Hypercube,” contributed problem in Oberwolfach Reports 22 (2025), no. 1, 405–450, at p. 445. DOI.
- P. Austrin, H. Chung, K.-M. Chung, S. Fu, Y.-T. Lin and M. Mahmoody, On the Impossibility of Key Agreements from Quantum Random Oracles, CRYPTO 2022, LNCS 13508, 165–194. DOI.
- L. Li, Q. Li, X. Li and Q. Liu, Impossibility of Perfectly Complete Many-Round Key Agreement in the QROM, 4 August 2026, Lemma 3.5, pp. 7–8. arXiv:2608.03824v1.
- R. Kothari, M. Kovacs-Deak, D. Wang and R. Z. Yang, Rational degree is polynomially related to degree, 28 September 2026, Fact 5, Theorem 1 and Corollary 1. arXiv:2601.08727v3.
- R. O’Donnell, M. Saks, O. Schramm and R. A. Servedio, Every decision tree has an influential variable, FOCS 2005, 31–39; §3.3, Eq. (6), p. 8 in the preprint. DOI · arXiv:cs/0508071v1.
Status and collaboration
AI tools were used extensively in developing, writing, reproducing and reviewing this work. The preprint is unrefereed. Internal AI-assisted reviews are not external human peer review, journal acceptance or proof-assistant certification.
Independent verification, substantive mathematical extensions and journal preparation would be useful contributions to further work. Collaboration and authorship would be based on actual contributions.