Restrictions of Infinite Circuits
Abstract
We present a new approach to lower bounds on Borel rank via a connection between Borel sets and infinite circuits. We prove an infinite analog to Håstad's switching lemma called the \emph{restriction lemma}, which shows that by fixing the values of some inputs, we can simultaneously reduce the complexity of one Borel function while largely maintaining the complexity of another. This result provides a purely combinatorial proof of the Borel hierarchy theorem, as well as simple proofs of various Ramsey-like properties of Borel sets and functions. We prove that the restriction lemma is sharp and also discuss counterexamples demonstrating the limitations of the restriction technique, in the context of both Borel functions and AC0 circuit families.
Related
- When light travels with infinite speed: the electromagnetic loop circuits
- Brauer--Manin obstruction for Weil restrictions
- Dual mixing and quasi-mixing of inner function restrictions
- On partitions with bounded multiplicity restrictions on even parts and with the largest part being odd
- Refutable Exclusion Restrictions in Competing Risks with Categorical Covariates
BibTeX
@misc{leach2026restrictions,
title = {{Restrictions of Infinite Circuits}},
author = {Evan Leach},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14039},
eprint = {2609.14039},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14039},
}
RIS
TY - UNPB
TI - Restrictions of Infinite Circuits
AU - Evan Leach
PY - 2026
DA - 2026/09/12
PB - arXiv
DO - 10.48550/arxiv.2609.14039
UR - https://arxiv.org/abs/2609.14039
AB - We present a new approach to lower bounds on Borel rank via a connection between Borel sets and infinite circuits. We prove an infinite analog to Håstad's switching lemma called the \emph{restriction lemma}, which shows that by fixing the values of some inputs, we can simultaneously reduce the complexity of one Borel function while largely maintaining the complexity of another. This result provides a purely combinatorial proof of the Borel hierarchy theorem, as well as simple proofs of various Ramsey-like properties of Borel sets and functions. We prove that the restriction lemma is sharp and also discuss counterexamples demonstrating the limitations of the restriction technique, in the context of both Borel functions and AC^0 circuit families.
ER -