Encoding orders and trees in real-valued functions

G Conant, C Terry

arXiv:2607.21761v1 Primary: math.CO Secondary: cs.LG, math.LO

Abstract

We prove function-theoretic analogues of a quantitative result of Hodges on extracting the order property from a sufficiently large 2-tree coded in a binary relation. Similar analogues for functions were previously obtained by Daskalakis and Golowich and by Anderson and Benedikt. These results are from statistical learning theory, where 2-trees are captured by sequential fat-shattering dimension, and the order property is controlled by various notions of "thresholds". Our first main result (Theorem 1.11) focuses on extracting a less restrictive kind of threshold from a tree, and yields significantly better bounds compared to what can be obtained from earlier results focusing on more restrictive versions. Part of the motivation for Theorem 1.11 lies in a companion paper, where this theorem is used to obtain efficient bounds in quantitative regularity lemmas for "stable functions". Here will use Theorem 1.11 to reprove a result of Anderson and Benedikt in a stronger form and with improved bounds. We also use Theorem 1.11 to prove an at most double-exponential bound on dual sequential fat-shattering, which resolves an open problem. In our second main result (Theorem 1.14), we give a new proof of a result of Daskalakis and Golowich on extracting "tight thresholds" from large sequential fat-shattering dimension, with improved bounds. This resolves another open problem related to correcting the proof of a result claimed by Jung, Kim, and Tewari.

Disclosure

“because of our particular indexing convention for trees (see the footnote prior to Definition 1.1). Acknowledgments Humans. The authors thank Aaron Anderson for comments on a preliminary draft. AI. ChatGPT was used for proofreading and for finding several relevant and useful results in the literature. It also made the following mathematical contributions: (1) Proposition 3.4 was provided by ChatGPT upon direct request. (2) Our original proof”
PDF page 26

Classification: Substantial mathematical content or result generation
Multiplier: 10
Verified: 2026-08-23T19:04:16.125961Z

Structural counts

Pages 27 pdf

Theorems 7 source

Lemmas 4 source

Propositions 7 source

Corollaries 4 source

Definitions 14 source

Displayed equations 65 source

Bibliography entries 22 source

Appendix pages 7 estimated

Count notes

Source counts use the expanded primary TeX file CT-hodges-arxiv1.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.