Neil Lutz

I&C Journal 2024 Journal Article

Projection theorems using effective dimension

• Neil Lutz
• D.M. Stull

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which states that for every analytic set E, for almost every line L, the Hausdorff dimension of the orthogonal projection of E onto L is maximal. We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E, even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing.

I&C Journal 2023 Journal Article

Extending the reach of the point-to-set principle

• Jack H. Lutz
• Neil Lutz
• Elvira Mayordomo

The point-to-set principle of J. Lutz and N. Lutz (2018) has recently enabled the theory of computing to be used to answer open questions about fractal geometry in Euclidean spaces R n. These are classical questions, meaning that their statements do not involve computation or related aspects of logic. In this paper we extend the reach of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces X. We first extend two algorithmic dimensions—computability-theoretic versions of classical Hausdorff and packing dimensions that assign dimensions dim ⁡ ( x ) and Dim ( x ) to individual points x ∈ X —to arbitrary separable metric spaces and to arbitrary gauge families. Our first two main results then extend the point-to-set principle to arbitrary separable metric spaces and to a large class of gauge families. We demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces.

I&C Journal 2020 Journal Article

Bounding the dimension of points on a line

• Neil Lutz
• D.M. Stull

We use Kolmogorov complexity methods to give a lower bound on the effective Hausdorff dimension of the point ( x, a x + b ), given real numbers a, b, and x. We apply our main theorem to a problem in fractal geometry, giving an improved lower bound on the (classical) Hausdorff dimension of generalized sets of Furstenberg type.

SODA Conference 2020 Conference Paper

Quantifying the Burden of Exploration and the Unfairness of Free Riding

• Christopher Jung 0001
• Sampath Kannan
• Neil Lutz

MFCS Conference 2018 Conference Paper

Projection Theorems Using Effective Dimension

• Neil Lutz
• Donald M. Stull

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which shows that for every analytic set E, for almost every line L, the Hausdorff dimension of the orthogonal projection of E onto L is maximal. We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E, even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing.

MFCS Conference 2017 Conference Paper

Fractal Intersections and Products via Algorithmic Dimension

• Neil Lutz

Algorithmic dimensions quantify the algorithmic information density of individual points and may be defined in terms of Kolmogorov complexity. This work uses these dimensions to bound the classical Hausdorff and packing dimensions of intersections and Cartesian products of fractals in Euclidean spaces. This approach shows that a known intersection formula for Borel sets holds for arbitrary sets, and it significantly simplifies the proof of a known product formula. Both of these formulas are prominent, fundamental results in fractal geometry that are taught in typical undergraduate courses on the subject.