Pith. sign in

REVIEW 2 major objections 4 minor 37 references

Algorithmic Information Bounds for Distances and Orthogonal Projections

T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read Two independent planar points share at least half of their algorithmic information through the distance between them.

desk verdict Novel, important bounds, but both main proofs have a load-bearing gap in the reconstruction step: the sparsity of P_u/P_v is asserted, not proven. read the letter →

arxiv 2509.05211 v2 pith:YHTHQCK2 submitted 2025-09-05 cs.CC math.CA

Peter Cholak , Marianna Csörnyei , Neil Lutz , Patrick Lutz , Elvira Mayordomo , D. M. Stull This is my paper · ORCID
classification cs.CCmath.CA MSC 68Q3028A8003D32
keywords Kolmogorovcomplexityfinite-precisionHausdorffdimensionpinneddistancesetsorthogonalprojectionseffectivepoint-to-setprincipleexceptional
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes quantitative half-information theorems for the plane. If two points x and y are sufficiently independent—meaning y's oracle does not lower the finite-precision complexity of x by more than a small linear amount—then the distance |x−y| carries at least half of the algorithmic information content of x, up to lower-order terms (Theorem 2). The same holds for the coordinate of x under orthogonal projection onto a direction e that is sufficiently independent of x (Theorem 3). Because the bounds are quantitative and relativize to arbitrary oracles, the point-to-set principle turns them into measure-theoretic statements: every analytic planar set E of Hausdorff dimension s≤1 has a point whose pinned distance set has dimension at least 3s/4, and the exceptional directions that lose more than half the dimension form a dimension-zero set. A new surrogate-point selection step, driven by a double-counting lemma, is what makes the proofs work.

What carries the argument

The load-bearing objects are finite-precision Kolmogorov complexities: K_r(x) is the length of the shortest program that outputs a rational point within 2^{−r} of x, and K^{A,y}_{r,s}(·|·) conditions on coarser approximations and oracles. The proofs run through a combinatorial surrogate-selection lemma: from a large family of candidate points that share x's information profile, a double-counting argument (Cauchy–Schwarz) guarantees two centers u,v and a candidate d such that d is information-rich relative to u,v while the two directions from d to u and v are separated. The distance theorem then reconstructs d from the intersection of two thin annuli, using an annulus-intersection bound that

What would settle it

Fix r,s,x,y satisfying (14) with δ<ε/6·dim^{A,y}(e_{y,x}) and compute both sides of (15); a failure of the inequality at large r would falsify Theorem 2. Concretely, one can probe the proof's load-bearing step by enumerating the outputs U^u(π_u,d_u) over d_u∈D_s for a shortest witness π_u: if the same s-dyadic interval receives two distinct outputs on different inputs, the O(1) bound on P_{u,v} fails and the reconstruction chain (19) would need a different justification.

Watch

Extended reading notes

Core claim

The paper's central claim is that a single scalar measurement—the radius of a circle on which x lies, or the signed coordinate of x on a line—retains at least half of the algorithmic information in x whenever the auxiliary center or direction is independent of x. Formally, for all oracles A, points x,y in R^2, and large precisions r,s with K^{A,y}_r(x) ≥ K^A_r(x) − δr and δ < (ε/6) dim^{A,y}(e_{y,x}), the paper proves K^{A,y}_{r,s}(|x−y| | |x−y|) ≥ K^A_{r,s}(x|x)/2 − εr; the projection version replaces y by a direction e and uses δ < ε dim^A(e)/4. From the distance bound and the point-to-set principle, the paper derives Theorem 4: for every analytic E⊆R^2 with dim_H(E)=s≤1, sup_{x∈E} dim_H(∆

Load-bearing premise

In the distance proof (Section 4) the reconstruction step assumes that each shortest-witness program for a conditional complexity emits at most one candidate distance per precision interval, so the pair-candidate set is O(1); if one program could emit several candidates in the same interval on different inputs, the central half-information inequality would not follow.

Editorial extensions

If this is right

  • Pinned distance sets: for every analytic planar E with dim_H(E)=s≤1, some x∈E has dim_H(∆_x E) ≥ 3s/4, improving all previous uniform lower bounds.
  • Projection exceptional sets: the collection of directions e for which dim_H(p_e E) < dim_H(E)/2 has Hausdorff dimension 0, now for the wider class of sets admitting optimal Hausdorff oracles.
  • The half-information inequalities are conditional and quantitative, so they can serve as lemmas in multi-scale case analyses across precision intervals.
  • Both measurements—radial distance and projected coordinate—are information-dense: they discard at most half of the point's algorithmic information.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The surrogate-selection lemma looks transferable to other pairs of scalar measurements whose joint preimage has bounded multiplicity, which would yield half-information bounds for a wider family of geometric queries (not claimed in the paper).
  • Iterating the argument at several precision scales could plausibly raise the 3/4 constant, though the paper does not pursue this.
  • In R^n, reconstructing a point from n distances or n projections has finite multiplicity, so an analogous combinatorial lemma may give a family of higher-dimensional bounds; this is an extension, not a paper claim.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper develops quantitative algorithmic information bounds for distances and orthogonal projections in the plane. It claims that under mild independence conditions the distance |x-y| and a projection coordinate p_e x each retain at least half the finite-precision Kolmogorov complexity of x. The proofs use a combinatorial lemma (surrogate point selection) and prior effective-dimension techniques. From these bounds the paper derives new geometric measure theory results: pinned distance sets of analytic E⊂R^2 with dim_H E ≤ 1 satisfy sup_x dim_H Δ_x E ≥ (3/4) dim_H E, and a generalization of Bourgain's exceptional-sets theorem for projections to sets with optimal Hausdorff oracles.

Significance. If the main inequalities (15) and (21) were established, the paper would deliver a substantial improvement over the best previously known pinned-distance bounds of Shmerkin–Wang and Fiedler–Stull, and a new proof/generalization of Bourgain's theorem. The surrogate-point selection technique and the use of optimal Hausdorff oracles are interesting and potentially reusable. The paper is clearly written and the overall strategy is coherent. However, the proof of both main theorems currently contains an unsupported and in general false assertion about the candidate sets P_u and P_v; until that is repaired, the central claims are not established.

major comments (2)
  1. [Section 4, proof of Theorem 2, Eq. (19)] The assertion that each s-dyadic interval contains at most one element of P_u = {U^u(π_u,d_u) : d_u∈D_s} and similarly P_v is not justified and is false for arbitrary witnesses. A program witnessing a single conditional complexity can behave arbitrarily on other inputs and can output many values in the same s-interval; D_s is infinite, so P_u may even be dense. Hence |P_{u,v}| need not be O(1); it can be as large as 2^{r-s}. This O(1) bound is load-bearing for (19): selecting the correct pair would require extra bits and destroy the inequality. The same issue affects (24) in Section 5. A local repair is available by recovering the inputs to π_u,π_v from ⌊d⌋_s and the oracles with O(1) bits, since distance/projection maps are 1-Lipschitz; as written, the proof is incomplete.
  2. [Section 5, proof of Theorem 3, Eq. (24)] The same unsupported sparsity assertion is used to claim that P_{u,v} has cardinality O(1) in the projection argument. This is needed for inequality (24). Since Theorem 3 is used directly to prove Theorem 5 and also (through Theorem 13) Theorem 4, this gap affects the geometric measure theory consequences as well. The steps leading to (24) should be repaired or replaced, for instance by the direct-input-recovery argument sketched above.
minor comments (4)
  1. [Section 2.2] The notation D_s is introduced but 's-dyadic interval' is used without definition. It should be stated explicitly that this means an interval of the form [k/2^s, (k+1)/2^s).
  2. [Section 4] In the definition of V_1, the existential quantifier over v∈R^2 is non-constructive; the subsequent choice of v_d is not shown to be unique. This is acceptable for an existence argument, but a sentence clarifying that only existence is needed would help.
  3. [Appendix D] In the proof of Theorem 13, the inequality labeled (36) is stated as a target and then 'Combining this with (38) and (35)' is slightly confusing because (36) is what is being proved. Reorganize the flow.
  4. [Throughout] The phrase 'at least half the complexity' is informal; Theorems 2 and 3 contain an εr lower-order term, so the informal summary should be qualified (e.g., 'up to lower-order terms') in the introduction as well as the abstract.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivations are self-contained; prior self-citations are independent, and the flagged sparsity issue is a proof gap, not a definitional reduction.

full rationale

The paper's main derivations (Theorems 2 and 3) are carried out within the paper itself: they construct finite candidate sets X, V, and N_v, apply the combinatorial Lemma 1, use Wolff's annulus-intersection lemma, and then derive the reconstruction inequalities (19) and (24). The target quantities K_{r,s}(x|x) appear on both sides of the contradiction argument only because the proof assumes the negation of the conclusion and then derives a contradiction; this is standard proof by contradiction, not circularity. The subsequent Hausdorff-dimension results (Theorems 4 and 5) do rely on previous results by overlapping authors ([8], [22], [35], [6]), but those are previously established theorems with independent proofs and are not fitted parameters or definitions crafted to force the present conclusion. The skeptical concern about the assertion that each s-dyadic interval contains at most one element of P_u and P_v is a potential correctness gap in the proof of Theorem 2/3, not a circular step: it does not make the conclusion equivalent to an input by construction, nor does it rename a known result. Therefore no load-bearing circular step is exhibited, and the honest finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

No free parameters fitted to data; the paper is a pure mathematical derivation. It relies on a network of prior effective-dimension results, several by the same authors, listed above.

assumptions (8)
  • domain assumption Point-to-set principle (J. Lutz and N. Lutz [14], Eq. 10)
    Used to pass from individual point complexities to Hausdorff dimension of sets (Sections 2.3, 6).
  • standard math Wolff's annulus intersection lemma (Appendix A, Lemma 6)
    Bounds the intersection of two thin annuli; cited from [37] and stated without proof.
  • domain assumption Lutz-Stull oracle lemma (Lemma 7, from [22])
    Provides an oracle D with specified complexity properties; used in Theorem 13 proof.
  • domain assumption Observations 8, 9, 10 from Stull [35]
    Geometric and complexity facts about distances and projections used in Theorem 13.
  • domain assumption Fiedler-Stull Lemma 11 [8]
    Relates complexity of y to complexity of distance |x-y|; used in Theorem 13.
  • domain assumption Csornyei-Stull Lemma 12 [6]
    Bounds conditional complexity of x given projection and direction; used in Theorem 13.
  • domain assumption Existence of points x,y,e in F satisfying C1-C4, 'as shown in [8]'
    This is the bridge in Theorem 4 from Theorem 13 to the pinned-distance bound; relies on results in [8].
  • domain assumption Optimal Hausdorff oracles exist for analytic sets (Stull [34])
    Used in Theorem 5 to extend Bourgain's theorem beyond analytic sets.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Algorithmic Information Bounds for Distances and Orthogonal Projections." pith.science (2026). https://pith.science/paper/YHTHQCK2

@misc{pith2026250905211,
  author       = {Pith},
  title        = {Pith review of: Algorithmic Information Bounds for Distances and Orthogonal Projections},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YHTHQCK2}},
  note         = {Machine review of arXiv:2509.05211}
}
abstract

We introduce a new technique for proving bounds on the Kolmogorov complexity of geometric objects in Euclidean space, such as points and lines. We apply this technique to prove two theorems on algorithmic information theory, both of which have consequences for well-known problems in geometric measure theory. First, we show that for any point $x$ in the plane and any other point $y$ sufficiently independent of $x$, the distance between $x$ and $y$ retains at least half the complexity of the original point $x$. By the point-to-set principle of J. Lutz and N. Lutz, this yields an improved lower bound on the Hausdorff dimension of pinned distance sets, a topic closely related to Falconer's distance set conjecture. Second, we prove an analogous result for orthogonal projections: for any point $x$ in the plane and any line through the origin which is sufficiently independent of $x$, the projection of $x$ onto that line retains at least half the complexity of $x$. As a consequence, we obtain a generalization of a theorem of Bourgain on exceptional sets for orthogonal projections.

Figures

Figures reproduced from arXiv: 2509.05211 by the authors.

Figure 1
Figure 1. Pinned distance set lower bounds for dimH(E) ∈ [0, 1]. Theorem 5 (generalizing Bourgain [2]). Let E ⊆ R 2 , and suppose that optimal Hausdorff oracles for E exist. Then dimH  e ∈ S1 [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 20 canonical work pages

  1. [1]

    Distance sets bounds for polyhedral norms via effective dimension

    Iqra Altaf, Ryan Bushling, and Bobby Wilson. Distance sets bounds for polyhedral norms via effective dimension, 2024.arXiv:2305.06937

    work page Pith review arXiv 2024

  2. [2]

    The discretized sum-product and projection theorems.J

    Jean Bourgain. The discretized sum-product and projection theorems.J. Anal. Math., 112:193–236, 2010. doi:10.1007/s11854-010-0028-x

    doi:10.1007/s11854-010-0028-x 2010

  3. [3]

    Ryan E. G. Bushling and Jacob B. Fiedler. Bounds on the dimension of lineal extensions, 2024. arXiv:2404.16315

    work page Pith review arXiv 2024

  4. [4]

    Adam Case and Jack H. Lutz. Mutual dimension.ACM Transactions on Computation Theory, 7(3):12, 2015. doi:10.1145/2786566

    doi:10.1145/2786566 2015

  5. [5]

    Peter Cholak, Marianna Cs¨ ornyei, Neil Lutz, Patrick Lutz, Elvira Mayordomo, and D. M. Stull. Bounding the dimension of exceptional sets for orthogonal projections, 2024.arXiv:2411.04959. 12 P. CHOLAK, M. CS ¨ORNYEI, N. LUTZ, P. LUTZ, E. MAYORDOMO, AND D. STULL

    work page Pith review arXiv 2024

  6. [6]

    Marianna Csornyei and D. M. Stull. Improved bounds for radial projections in the plane, 2025. arXiv:2508.18228

    arXiv 2025

  7. [7]

    Fiedler and D

    Jacob B. Fiedler and D. M. Stull. Dimension of pinned distance sets for semi-regular sets, 2023. arXiv:2309.11701

    arXiv 2023

  8. [8]

    Fiedler and D

    Jacob B. Fiedler and D. M. Stull. Pinned distances of planar sets with low dimension, 2024. arXiv:2408.00889

    arXiv 2024

Show all 37 references
  1. [9]

    Fiedler and D

    Jacob B. Fiedler and D. M. Stull. Universal sets for projections, 2024.arXiv:2411.16001

    2024 arXiv

  2. [10]

    On Hausdorff dimension of projections.Mathematika, 15:153–155, 1968

    Robert Kaufman. On Hausdorff dimension of projections.Mathematika, 15:153–155, 1968. doi:10.1112/ S0025579300002503

    1968

  3. [11]

    Ming Li and Paul M. B. Vit´ anyi.An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, Berlin, 2019. Fourth Edition.doi:10.1007/978-3-030-11298-1

    2019 doi

  4. [12]

    Jack H. Lutz. The dimensions of individual strings and sequences.Information and Computation, 187(1):49–79, 2003.doi:10.1016/S0890-5401(03)00187-1

    2003 doi

  5. [13]

    Lutz and Neil Lutz

    Jack H. Lutz and Neil Lutz. Lines missing every random point.Computability, 4(2):85–102, 2015. doi:10.3233/ COM-150038

    2015

  6. [14]

    Lutz and Neil Lutz

    Jack H. Lutz and Neil Lutz. Algorithmic information, plane Kakeya sets, and conditional dimension.ACM Transactions on Computation Theory, 10(2):7:1–7:22, 2018.doi:10.1145/3201783

    2018 doi

  7. [15]

    Lutz, Neil Lutz, and Elvira Mayordomo

    Jack H. Lutz, Neil Lutz, and Elvira Mayordomo. Dimension and the structure of complexity classes.Theory of Computing Systems, 67(2):473–490, 2023.doi:10.1007/s00224-022-10096-7

    2023 doi

  8. [16]

    Lutz, Neil Lutz, and Elvira Mayordomo

    Jack H. Lutz, Neil Lutz, and Elvira Mayordomo. Extending the reach of the point-to-set principle.Information and Computation, 294:105078, 2023.doi:10.1016/j.ic.2023.105078

    2023

  9. [17]

    Lutz, Renrui Qi, and Liang Yu

    Jack H. Lutz, Renrui Qi, and Liang Yu. The point-to-set principle and the dimensions of Hamel bases.Com- putability, 13(2):105–112, 2024.doi:10.3233/COM-210383

    2024 doi

  10. [18]

    Fractal intersections and products via algorithmic dimension.ACM Transactions on Computation Theory, 13(3), August 2021.doi:10.1145/3460948

    Neil Lutz. Fractal intersections and products via algorithmic dimension.ACM Transactions on Computation Theory, 13(3), August 2021.doi:10.1145/3460948

    2021 doi

  11. [19]

    Lineal extensions of Kakeya sets missing every ee-random point, 2025.arXiv:2507.05475

    Neil Lutz, Spencer Park Martin, and Rain White. Lineal extensions of Kakeya sets missing every ee-random point, 2025.arXiv:2507.05475

    2025

  12. [20]

    Neil Lutz and D. M. Stull. Bounding the dimension of points on a line.Information and Computation, 275:104601, 2020.doi:10.1016/j.ic.2020.104601

    2020

  13. [21]

    Neil Lutz and D. M. Stull. Dimension spectra of lines.Computability, 11(2):85–112, 2022. doi:10.3233/ COM-190292

    2022

  14. [22]

    Neil Lutz and D. M. Stull. Projection theorems using effective dimension.Information and Computation, 297:105137, 2024.doi:10.1016/j.ic.2024.105137

    2024

  15. [23]

    J. M. Marstrand. Some fundamental geometrical properties of plane sets of fractional dimensions.Proc. London Math. Soc. (3), 4:257–302, 1954.doi:10.1112/plms/s3-4.1.257

    1954 doi

  16. [24]

    Cambridge University Press, 1999.doi:10.1017/CBO9780511623813

    Pertti Mattila.Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Cambridge University Press, 1999.doi:10.1017/CBO9780511623813

    1999 doi

  17. [25]

    Hausdorff dimension, projections, intersections, and Besicovitch sets

    Pertti Mattila. Hausdorff dimension, projections, intersections, and Besicovitch sets. InNew Trends in Applied Harmonic Analysis, Volume 2, pages 129–157. Springer, 2019.doi:10.1007/978-3-030-32353-0_6

    2019 doi

  18. [26]

    Mayordomo

    E. Mayordomo. A Kolmogorov complexity characterization of constructive Hausdorff dimension.Information Processing Letters, 84(1):1–3, 2002.doi:10.1016/S0020-0190(02)00343-5

    2002 doi

  19. [27]

    A point to set principle for finite-state dimension

    Elvira Mayordomo. A point to set principle for finite-state dimension. In Arnold Beckmann, Isabel Oitavem, and Florin Manea, editors,Crossroads of Computability and Logic: Insights, Inspirations, and Innovations, pages 299–304, Cham, 2025. Springer Nature Switzerland.doi:10.10...

    2025 doi

  20. [28]

    Fractal dimensions and profinite groups, 2025.arXiv:2502.09995

    Elvira Mayordomo and Andre Nies. Fractal dimensions and profinite groups, 2025.arXiv:2502.09995

    2025

  21. [29]

    Point-to-set principle and constructive dimension faithfulness

    Satyadev Nandakumar, Subin Pulari, and Akhil S. Point-to-set principle and constructive dimension faithfulness. In Rastislav Kr´ aloviˇ c and Anton ´ ın Kuˇ cera, editors,49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 ofLei...

    2024

  22. [30]

    Furstenberg sets estimate in the plane, 2023.arXiv:2308.08819

    Kevin Ren and Hong Wang. Furstenberg sets estimate in the plane, 2023.arXiv:2308.08819

    2023 arXiv

  23. [31]

    Inequalities for entropies and dimensions

    Alexander Shen. Inequalities for entropies and dimensions. In Gianluca Della Vedova, Besik Dundua, Steffen Lempp, and Florin Manea, editors,Unity of Logic and Computation, pages 120–131, Cham, 2023. Springer Nature Switzerland.doi:10.1007/978-3-031-36978-0_10

    2023 doi

  24. [32]

    A non-linear version of Bourgain’s projection theorem: Dedicated to the memory of Jean Bourgain

    Pablo Shmerkin. A non-linear version of Bourgain’s projection theorem: Dedicated to the memory of Jean Bourgain. Journal of the European Mathematical Society (EMS Publishing), 25(10), 2023.doi:10.4171/JEMS/1283

    2023 doi

  25. [33]

    On the distance sets spanned by sets of dimension d/2 in Rd, 2021

    Pablo Shmerkin and Hong Wang. On the distance sets spanned by sets of dimension d/2 in Rd, 2021. arXiv: 2112.09044

    2021 arXiv

  26. [34]

    D. M. Stull. Optimal oracles for point-to-set principles. In39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 57:1–57:17, 2022.doi:10.4230/LIPIcs.STACS.2022.57

    2022 doi

  27. [35]

    D. M. Stull. Pinned distance sets using effective dimension, 2022.arXiv:2207.12501. ALGORITHMIC INFORMATION BOUNDS FOR DISTANCES AND ORTHOGONAL PROJECTIONS 13

    2022 arXiv

  28. [36]

    D. M. Stull. The dimension spectrum conjecture for planar lines.Journal of the London Mathematical Society, 111(6):e70216, 2025.doi:10.1112/jlms.70216

    2025 doi

  29. [37]

    A Kakeya-type problem for circles.American Journal of Mathematics, 119(5):985–1026, 1997

    Thomas Wolff. A Kakeya-type problem for circles.American Journal of Mathematics, 119(5):985–1026, 1997. doi:10.1353/ajm.1997.0034. AppendixA.Wolff’s Annulus Intersection Lemma Lemma 6(Wolff [ 37]).Let ρ1, ρ2 ∈ [0.99, 1.01], x1, x2 ∈ [0, 0.01]2, and ε >0. Let A1 and A2 be the o...

    1997

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.