A forced coordinate with nearly maximal erasure entropy

The erasure entropy $E_x(f)$ of a Boolean function at a coordinate $x$ is the conditional entropy of the event $x\in U$ given $U\setminus\{x\}$, where $U$ is drawn from the spectral distribution, and it never exceeds the binary entropy of the influence $\mathrm{Inf}_x(f)$. We study an explicit monotone function on $2k+1$ variables in which one coordinate $x$ is the only variable lying both in a shortest minterm and in a shortest maxterm. It is obtained from a majority function with one hidden coordinate by replacing half of the majority's inputs with the OR of two fresh variables and the other half with the AND of two. We prove that $E_x/\mathrm{Inf}_x=(1+o(1))\log_2(1/\mathrm{Inf}_x)=(1+o(1))(k-1)\log_2\frac43$, so the ratio at the forced coordinate grows linearly in $k$ and is asymptotic to its largest possible value. The proof writes the relevant biased Fourier coefficients of the majority as integrals over the unit circle, on which the integrand has an explicit modulus with a single pair of peaks, and uses that the phase advances by $\arccos\frac13$, an irrational multiple of $\pi$, from one class of coefficients to the next.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-11
DOI
https://doi.org/10.5281/zenodo.24126356
Primary Topic
Coding theory and cryptography
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

A forced coordinate with nearly maximal erasure entropy

Yitzchak Shmalo
Zenodo (CERN European Organization for Nuclear Research)
Coding theory and cryptography
preprint

A forced coordinate with nearly maximal erasure entropy

Yitzchak Shmalo
preprint en

Abstract

The erasure entropy $E_x(f)$ of a Boolean function at a coordinate $x$ is the conditional entropy of the event $x\in U$ given $U\setminus\{x\}$, where $U$ is drawn from the spectral distribution, and it never exceeds the binary entropy of the influence $\mathrm{Inf}_x(f)$. We study an explicit monotone function on $2k+1$ variables in which one coordinate $x$ is the only variable lying both in a shortest minterm and in a shortest maxterm. It is obtained from a majority function with one hidden coordinate by replacing half of the majority's inputs with the OR of two fresh variables and the other half with the AND of two. We prove that $E_x/\mathrm{Inf}_x=(1+o(1))\log_2(1/\mathrm{Inf}_x)=(1+o(1))(k-1)\log_2\frac43$, so the ratio at the forced coordinate grows linearly in $k$ and is asymptotic to its largest possible value. The proof writes the relevant biased Fourier coefficients of the majority as integrals over the unit circle, on which the integrand has an explicit modulus with a single pair of peaks, and uses that the phase advances by $\arccos\frac13$, an irrational multiple of $\pi$, from one class of coefficients to the next.

Zenodo (CERN European Organization for Nuclear Research)
Hebrew University of Jerusalem (IL)
Coding theory and cryptography
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon