Pith. sign in

REVIEW 1 major objections 1 minor 13 references

The Fourier Entropy-Influence conjecture holds for δ-tribes functions, monotone functions with the tribe separation property, and functions with the semi-separation property.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

The authors prove that δ-tribes functions, monotone Boolean functions with the tribe separation property, and Boolean functions with the semi-separation property satisfy the FEI conjecture using a stopping binary tree and a key entropy-influence inequality.

T0 review reviewed 2026-06-28 challenge →

load-bearing objection The paper adds three more families to the verified cases for the FEI conjecture using a stopping binary tree reduction. the 1 major comments →

arxiv 2606.00246 v2 pith:T2QVNKSN submitted 2026-05-29 math.CO cs.DMmath.CA

Further evidence towards the Fourier Entropy-Influence conjecture

Mar\'ia Jos\'e Gonz\'alez , Paul MacManus , Mar\'ia Cristina Pereyra This is my paper
classification math.CO cs.DMmath.CA
keywords Fourier Entropy-Influence conjectureBoolean functionstribes functionsmonotone functionsFourier analysisinfluenceentropyseparation property
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The Fourier Entropy-Influence conjecture states that the Fourier entropy of any Boolean function is at most its total influence. The paper verifies the conjecture for several new families by introducing a stopping binary tree and a key inequality that relates entropy differences of a function and its subfunctions to the m-influence. Functions in the identified classes satisfy the inequality at every branching node of the tree and the conjecture itself at the stopping nodes. This recursive structure yields the result for the whole function. The approach shows how the conjecture can be established class by class without proving the general case.

Core claim

The authors establish that δ-tribes functions, monotone Boolean functions with the tribe separation property, and Boolean functions with the semi-separation property all satisfy the Fourier Entropy-Influence conjecture. They do so by defining a stopping binary tree such that any function obeying the key inequality at its branching nodes and the conjecture at its stopping nodes obeys the conjecture overall. These three classes are shown to meet both requirements.

What carries the argument

The stopping binary tree together with the key inequality that bounds the difference between the entropy of f and the average entropy of the subfunctions f± by the m-influence of f.

Load-bearing premise

The key inequality holds at the branching nodes of the stopping binary tree for the identified function classes.

What would settle it

A function belonging to one of the three classes in which Fourier entropy exceeds total influence, or in which the key inequality fails to hold at any branching node of its stopping binary tree.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The Fourier Entropy-Influence conjecture holds for every δ-tribes function.
  • The Fourier Entropy-Influence conjecture holds for every monotone Boolean function with the tribe separation property.
  • The Fourier Entropy-Influence conjecture holds for every Boolean function with the semi-separation property.
  • If the key inequality holds at every branching node for every Boolean function, then the Fourier Entropy-Influence conjecture holds for all Boolean functions by induction on the stopping binary tree.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation properties may indicate a structural condition on how influences are distributed across coordinates that makes the key inequality easier to verify.
  • The same tree-based reduction could be tested on additional families such as read-k functions or symmetric functions to see whether the inequality continues to hold.
  • If the key inequality turns out to fail for some functions, those counterexamples would isolate the precise obstacle to a general proof.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 1 minor

Summary. The paper introduces a stopping binary tree framework for the Fourier Entropy-Influence (FEI) conjecture: the conjecture holds for a Boolean function if a key inequality (bounding the difference H(f) − (H(f+) + H(f−))/2 by Inf_m(f)) holds at branching nodes and the conjecture holds at stopping nodes. The authors identify three classes—δ-tribes functions, monotone Boolean functions with the tribe separation property, and Boolean functions with the semi-separation property—that fit suitably chosen trees in this framework and thereby satisfy the FEI conjecture.

Significance. If the claimed verifications of the key inequality hold, the work supplies new, explicitly described classes of functions satisfying the FEI conjecture beyond the previously known symmetric functions and read-k decision trees. The stopping-binary-tree reduction is a non-circular structural device that isolates the inequality as the only additional condition needed; this may prove useful for further targeted verifications. The paper also records auxiliary results on these classes that could be of independent interest to experts.

major comments (1)
  1. [Abstract / framework description] The central claim that the three listed classes satisfy the FEI conjecture rests entirely on the assertion that the key inequality holds at the branching nodes of the chosen stopping trees. The manuscript states that the classes 'fit this framework' and 'demonstrate that they satisfy' the conjecture, but does not exhibit the explicit calculations or case analysis establishing the inequality for δ-tribes or the separation properties; this verification is load-bearing for the result.
minor comments (1)
  1. [Abstract] Abstract contains the typographical repetition 'and, and,' in the sentence listing the three classes.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful summary and for highlighting the potential utility of the stopping-binary-tree framework. We address the single major comment below.

read point-by-point responses

  1. Referee: [Abstract / framework description] The central claim that the three listed classes satisfy the FEI conjecture rests entirely on the assertion that the key inequality holds at the branching nodes of the chosen stopping trees. The manuscript states that the classes 'fit this framework' and 'demonstrate that they satisfy' the conjecture, but does not exhibit the explicit calculations or case analysis establishing the inequality for δ-tribes or the separation properties; this verification is load-bearing for the result.

    Authors: We agree that the explicit verification of the key inequality at branching nodes is load-bearing and that the current manuscript does not contain the full case analysis. In the revised version we will insert detailed calculations establishing the inequality for each of the three classes (δ-tribes, monotone functions with the tribe-separation property, and functions with the semi-separation property), including the choice of branching variable m at each node and the resulting entropy-influence bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces a stopping binary tree framework under which the FEI conjecture follows if a key inequality holds at branching nodes and the conjecture holds at stopping nodes. It then directly verifies that δ-tribes functions, monotone Boolean functions with the tribe separation property, and functions with the semi-separation property satisfy these conditions for suitably chosen trees. This constitutes a direct, class-specific verification rather than any reduction of the central claim to self-definitions, fitted inputs renamed as predictions, or load-bearing self-citations. The derivation chain is self-contained against external benchmarks with independent content.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claim rests on standard background facts from Fourier analysis on the hypercube together with the validity of the newly introduced key inequality for the specific classes; no numerical free parameters appear.

axioms (2)
  • standard math Standard properties of Fourier transforms, entropy, and influence for Boolean functions on the hypercube
    The paper builds directly on established results in Boolean Fourier analysis.
  • ad hoc to paper The key inequality relating entropy difference to m-influence holds at branching nodes for the target classes
    This inequality is the load-bearing sufficient condition introduced to enable the inductive argument.
invented entities (1)
  • stopping binary tree no independent evidence
    purpose: Recursive decomposition structure that isolates branching nodes where the key inequality is applied and stopping nodes where the conjecture is already known
    Newly defined concept used to organize the inductive proof for the three classes.

reviewed 2026-06-28 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Further evidence towards the Fourier Entropy-Influence conjecture." pith.science (2026). https://pith.science/paper/T2QVNKSN

@misc{pith2026260600246,
  author       = {Pith},
  title        = {Pith review of: Further evidence towards the Fourier Entropy-Influence conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T2QVNKSN}},
  note         = {Machine review of arXiv:2606.00246}
}
Share X Bluesky LinkedIn Reddit HN
abstract

The Fourier Entropy-Influence (FEI) conjecture states that the Fourier entropy of Boolean functions is uniformly bounded by their total influence. It has been verified for canonical examples such as disjoint tribes and for some classes of Boolean functions such as symmetric functions and read-$k$ decision trees (with a constant that depends linearly on $k$). In this note we present new classes of Boolean functions that verify the FEI conjecture. The key element is an inequality controlling the difference between the entropy of a function $f$ and the average of the entropies of $f^{\pm}$, the sub-functions obtained by setting $x_m=\pm1$ for some $m$, by the $m$-influence of $f$. If this key inequality were to hold for Boolean functions, then the full FEI conjecture would follow by induction. We introduce the notion of a stopping binary tree and observe that functions that satisfy the key inequality at the branching nodes of the tree and the FEI conjecture at the stopping nodes will satisfy the FEI conjecture. We identify some classes of functions that fit this framework: the $\delta$-tribes functions, the monotone Boolean functions with the tribe separation property, and the Boolean functions with the semi-separation property, and, and, along the way, demonstrate some results that we hope the experts in this fascinating field might find useful.

Figures

Figures reproduced from arXiv: 2606.00246 by Mar\'ia Cristina Pereyra, Mar\'ia Jos\'e Gonz\'alez, Paul MacManus.

Figure 1
Figure 1. Figure 1: The left and middle figures depict the same stopping binary tree. The right figure depicts a stopping binary tree for the same root function with stopping nodes at different levels, note that the stopping functions at level 2 are different from those in the first two trees. We say that f ∈ Bn is computable as a depth-0 decision tree if it is constantly −1 or 1. We inductively say that f is computable as a … view at source ↗
Figure 2
Figure 2. Figure 2: (a) Split w.r.t to xn+1. (b) Stopping tree split w.r.t Tk = {y1, y2, y3}. Proof. We will show that any δ-tribes function F can be represented by a stopping binary tree such that at the stopping nodes we have disjoint tribes functions and at the branching nodes we have δ-tribes functions for whom inequality (23) holds. As the FEI conjecture holds for disjoint tribes, by Ansatz 1.2 (more precisely by Corolla… view at source ↗
Figure 3
Figure 3. Figure 3: Trees illustrating Example 6.5 (left) and Example 6.6 (right). It is not hard to construct examples of monotone functions that are not disjoint tribes but that are tribe separated. For example, f ∈ B7 given by tribes T1 = {x1, x2}, T2 = {x2, x3}, T3 = {x4, x5, x7}, T4 = {x5, x6, x7} is tribe separated by x5. Definition 6.7. A monotone Boolean function f satisfies the tribe separation property if there is a… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 1 canonical work pages

  1. [1]

    Arunachalam, S

    S. Arunachalam, S. Chakraborty, M. Kouch\'y, N. Saurabh, and R. de Wolf, Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154 , pp. 45:1--45:19, Schloss Dagstuhl – Leibniz-Zentrum f\"ur Informatik (2020)

    2020

  2. [2]

    Ben-Or and N

    M. Ben-Or and N. Linial, Collective coin flipping. In Silvio Micali, editor, Randomness and Computation. Academic Press, New York, 1990

    1990

  3. [3]

    Chakraborty, R

    S. Chakraborty, R. Kulkarni, S. Lokam, and N. Saurabh, Upper bounds on Fourier entropy. In Electronic Colloquium on Computational Complexity TR13-052, 2013

    2013

  4. [4]

    Friedgut and G

    E. Friedgut and G. Kalai, Every monotone graph property has a sharp threshold. Proc. AMS, 124 (10):2993--3002, 1996

    1996

  5. [5]

    M. J. Gonz\'alez, Paul MacManus, M. C. Pereyra, Las funciones booleanas y el lema de Bonami. La Gaceta de la RME 28 , N\'um. 1, 51--88, 2025

    2025

  6. [6]

    Han, A New Bound for the Fourier-Entropy-Influence Conjecture

    X. Han, A New Bound for the Fourier-Entropy-Influence Conjecture. Combinatorica (2025) 45:4

    2025

  7. [7]

    J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 68--80, 1988

    1988

  8. [8]

    Kelman, G

    E. Kelman, G. Kindler, N. Lifshitz, D. Minzer, and M. Safra, Towards a Proof of the Fourier-Entropy Conjecture?. Geom. Funct. Anal. 30, 1097--1138 (2020)

    2020

  9. [9]

    Klivans, H

    A. Klivans, H. Lee, and A. Wan, Mansour’s Conjecture is true for random DNF formulas. In Proceedings of the 23rd Annual Conference on Learning Theory, 2010

    2010

  10. [10]

    O'Donnell, Analysis of Boolean Functions

    R. O'Donnell, Analysis of Boolean Functions. Originally published April 2014 by Cambridge University Press. May 2021 arXiv edition - arXiv: 2105.10386v1

    work page arXiv 2014

  11. [11]

    O’Donnell and L.-Y

    R. O’Donnell and L.-Y. Tan, A composition theorem for the Fourier Entropy- Influence conjecture. In Proceedings of the 40th International Colloquium on Automata, Languages and Programming, pages 780--791, 2013

    2013

  12. [12]

    O’Donnell, J

    R. O’Donnell, J. Wright, and Y. Zhou, The Fourier Entropy–Influence Conjecture for Certain Classes of Boolean Functions. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science 6755 . Springer, Berlin, Heidelberg, 2011

    2011

  13. [13]

    A. Wan, J. Wright, and C. Wu, Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture . ITCS’14, 67--80, 2014

    2014

This paper was first reviewed by grok-4.3 on June 28, 2026.