The Point-to-Set Principle and the dimensions of Hamel bases

Abstract

We prove that, for every $0 ⩽ s ⩽ 1$ , there is a Hamel basis of the vector space of reals over the field of rationals that has Hausdorff dimension s.

The logic of our proof is of particular interest. The statement of our theorem is classical; it does not involve the theory of computing. However, our proof makes essential use of algorithmic fractal dimension–a computability-theoretic construct–and the point-to-set principle of J. Lutz and N. Lutz (2018).

Keywords

Algorithmic fractal dimension Hamel bases Hausdorff dimension Point-to-Set Principle

1. Introduction

This brief paper is an intellectual export from the theory of computing to classical mathematics, i.e., mathematics not ostensibly involving the theory of computing. This introduction describes our main theorem and then explains how its proof uses computability theory.

Two fundamental theorems of linear algebra state that every vector space has a basis and that any two bases of a vector space have the same cardinality, which is called the dimension of the vector space. When the vector space has finite dimension, the proofs of these facts are completely constructive and are standard undergraduate fare [1,5]. However, in 1905, Hamel [7] used the axiom of choice to prove that these two theorems hold for all vector spaces.1

¹
In 1984, confirming a 1908 conjecture of Zermelo [27], Blass [2] proved that the existence of bases for all vector spaces implies the axiom of choice.

Accordingly, infinite bases of vector spaces are traditionally called Hamel bases.

The canonical case of Hamel bases is the vector space $R$ of real numbers over the field $Q$ of rational numbers. This case is the topic of the present paper, so here as in many papers, all “Hamel bases” are bases of $R$ over $Q$ . Hamel [7] showed that every Hamel basis must have the cardinality of the continuum. Sierpinski [23] showed that every Hamel basis has inner Lebesgue measure 0, whence every measurable Hamel basis has measure 0. Jones [8] showed that the Cantor middle-thirds set contains a Hamel basis (which thus has Lebesgue measure 0) and that no Hamel basis is analytic, i.e., $Σ_{1}^{1}$ . Numerous other investigations of Hamel bases have appeared in the literature.

In this paper we investigate the Hausdorff dimensions of Hamel bases. Our main theorem says that, for every real number $s \in [0, 1]$ , there is a Hamel basis with Hausdorff dimension exactly s.

Although our main theorem says nothing about the theory of computing, our proof of it uses algorithmic fractal dimension, which is a computability-theoretic construct. Specifically, the algorithmic dimension of a number $x \in R$ is $\begin{matrix} (1) & dim (x) = \underset{n \to \infty}{lim inf} K (x [0, \dots, n - 1]) / n, \end{matrix}$ where $x [0, \dots, n - 1]$ is the string consisting of the first n bits of the binary expansion of x, and $K (x [0, \dots, n - 1])$ is the Kolmogorov complexity of this string [10,18]. Since $K (x [0, \dots, n - 1])$ is the algorithmic information content of $x [0, \dots, n - 1]$ (and is where computability theory comes into the picture [4,9,22]), this says that $dim (x)$ is the lower asymptotic algorithmic information density of the real number x. This and related algorithmic fractal dimensions are discussed in the recent surveys [12,14].

The bridge between the above algorithmic dimension and our investigation of the Hausdorff dimensions of Hamel bases is the Point-to-Set Principle of J. Lutz and N. Lutz [11]. This principle gives complete pointwise characterizations of various classical fractal dimensions in terms of relativizations of their algorithmic counterparts. Specialized to the case of Hausdorff dimension in $R$ , this principle says that, for every set $E \subseteq R$ , $\begin{matrix} (2) & {dim}_{H} (E) = min_{A \subseteq N} sup_{x \in E} {dim}^{A} (x) . \end{matrix}$ That is, the classical Hausdorff dimension of a set E is the minimum, for all oracles A, of the supremum of the algorithmic dimensions, relative to A, of the individual points in E.

The Point-to-Set Principle is especially useful for proving otherwise difficult lower bounds on the Hausdorff dimensions of sets. It implies that, to prove a lower bound on the Hausdorff dimension of a set E, it suffices to let A be an arbitrary oracle and prove a corresponding lower bound on the algorithmic dimension, relative to A, of a judiciously chosen point in E. This ability to reason from the relativized dimensions of single points to the dimensions of entire sets has recently been used to prove several new theorems about classical fractal dimensions. Examples include stronger lower bounds on the Hausdorff dimensions of generalized Furstenberg sets [17]; extension of the fractal intersection formula from Borel sets to arbitrary sets [15]; the extension of Marstrand’s projection theorem from analytic sets to arbitrary sets, provided that their Hausdorff and packing dimensions coincide [16]; a proof that, if $V = L$ , then the maximal thin co-analytic set has Hausdorff dimension 1 [24]; a further relaxation of the hypothesis of Marstrand’s projection theorem [25]; and an improved bound on the Hausdorff dimensions of pinned distance sets [26].

An encouraging aspect of the above successes of the Point-to-Set Principle is that the proofs do not all look alike. The principle has turned out to be quite flexible, allowing investigators to invoke it in arguments appropriate to various settings. In the present paper we use it in the following way. Given a target dimension $s \in [0, 1]$ , we construct a Hamel basis B of $R$ over $Q$ by a transfinite recursion, putting a single real into B at each stage. At even stages, we add points to B that enable us to use the Point-to-Set Principle to conclude that B has Hausdorff dimension s. At odd stages, we ensure that B spans $R$ . The details appear in Section 3.

2. Preliminaries

All logarithms here are base-2. For $B \subseteq R$ , we write $span (B)$ for the linear span of B over $Q$ , i.e., the set of all linear combinations $\begin{matrix} x = \sum_{u \in I} g (u) u, \end{matrix}$ where $I \subseteq B$ is finite and $g : I \to Q ∖ {0}$ .

We refer to standard set theory texts, e.g., [6,19,21] or early sections of more advanced texts, for background on ordinal numbers and transfinite recursion. We write ω for the first infinite ordinal and $2^{ℵ_{0}}$ for the cardinality of the continuum.

For each $s \in (0, 1]$ , we define a Cantor set $C_{s} \subseteq [0, 1]$ that we use in the proof of our main theorem in Section 3. A set $C_{0}$ for the case $s = 0$ is defined separately below. The definitions and key properties of these sets appear in this preliminary section because they are well understood.

Fix $s \in (0, 1]$ , and let $r = 2^{- \frac{1}{s}}$ , noting that $r \in (0, \frac{1}{2}]$ . For each $i \in N$ , let $\begin{matrix} r_{i} = \{\begin{array}{ll} r & if r \in (0, \frac{1}{2}) \\ \frac{1}{2} - 2^{- (i + 2)} & if r = \frac{1}{2}, \end{array} \end{matrix}$ noting that $r = (r_{i} | i \in N)$ is a sequence in $(0, \frac{1}{2})$ that converges to r in any case.

Define a family ${I_{w} | w \in {0, 1}^{*}}$ of closed intervals $I_{w} \subseteq [0, 1]$ by the following recursion.

$I_{λ} = [0, 1]$ . (We write λ for the empty string.)

If $I_{w} = [a, b]$ , then $\begin{matrix} I_{w 0} = [a, a + r_{| w |} (b - a)] \end{matrix}$ and $\begin{matrix} I_{w 1} = [b - r_{| w |} (b - a), b] . \end{matrix}$

For each

k \in N

, let

\begin{matrix} C_{s, k} = ⋃_{w \in {0, 1}^{k}} I_{w}, \end{matrix}

and let

\begin{matrix} C_{s} = ⋂_{k = 0}^{\infty} C_{s, k} . \end{matrix}

Note that

C_{s}

is a “Cantor middle

1 - 2 r

set” and that

C_{\frac{1}{log 3}}

is the familiar Cantor middle-thirds set. In any case,

C_{s}

is a self-similar fractal whose Hausdorff dimension, by standard methods, is

\begin{matrix} {dim}_{H} (C_{s}) = \frac{- 1}{log r} = s . \end{matrix}

Moreover, each point

x \in C_{s}

is specified in the obvious manner by a unique coding sequence

T_{x} \in {0, 1}^{ω}

, and the main theorem of Lutz and Mayordomo [13] (relativized to an oracle for the real number r) tells us that

\begin{matrix} {dim}^{r} (x) = s {dim}^{r} (T_{x}) \end{matrix}

holds for each

x \in C_{s}

. In particular, since every sequence T in the set

{RAND}^{r}

of all sequences that are algorithmically random relative to r has dimension 1 relative to r, and since the set

{RAND}^{r}

has the cardinality of the continuum, it follows that the set

\begin{matrix} D^{r} = {x \in C_{s} | {dim}^{r} (x) = s} \end{matrix}

has the cardinality of the continuum. This entire argument relativizes, so for any oracle

A \subseteq N

from which r can be computed, the set

\begin{matrix} D^{A} = {x \in C_{s} | {dim}^{A} (x) = s} \end{matrix}

has the cardinality of the continuum.

The remaining property of $C_{s}$ that is needed for our argument in Section 4 is that $\begin{matrix} span (C_{s}) = R . \end{matrix}$ This follows immediately from the main result of Cabrelli, Hare, and Molter [3], which tells us that there exists N such that the N-fold sumset $\begin{matrix} C_{s} + \dots + C_{s} = {x_{1} + \dots + x_{N} | each x_{i} \in C_{s}} \end{matrix}$ contains an interval.

We now turn to the case $s = 0$ . For each binary sequence $b = (b_{i} | i \in N) \in {0, 1}^{ω}$ , let $\begin{matrix} supp (b) = {i \in N | b_{i} = 1} \end{matrix}$ be the support of b, let $\begin{matrix} \underline{den} (b) = \underset{n \to \infty}{lim inf} \frac{| supp (b) \cap {0, \dots, n - 1} |}{n} \end{matrix}$ be the lower asymptotic density of b, and let $\begin{matrix} x (b) = \sum_{i = 0}^{\infty} 2^{- (i + 1)} b_{i} \end{matrix}$ be the real number represented by b.

Let $\begin{matrix} C_{0} = {x (b) | b \in {0, 1}^{ω} and \underline{den} (b) = 0} . \end{matrix}$ It is well known [10] that $dim (x) = 0$ for all $x \in C_{0}$ , whence ${dim}_{H} (C_{0}) = 0$ . It is clear that $C_{0}$ has the cardinality of the continuum.

To see that $span (C_{0}) = R$ , let $x \in [0, 1]$ . It suffices to show that there exists $x_{0}, x_{1} \in C_{0}$ such that $x_{0} + x_{1} = x$ . For each $k \in N$ , let $m_{k} = k!$ , noting that $m_{k} = o (m_{k + 1} - m_{k})$ as $k \to \infty$ . Partition $N$ into the two sets $\begin{array}{c} J_{0} = ⋃_{k = 0}^{\infty} [m_{2 k}, m_{2 k + 1}), \\ J_{1} = ⋃_{k = 0}^{\infty} [m_{2 k + 1}, m_{2 k + 2}), \end{array}$ where the “intervals” here are the obvious sets of natural numbers. Fix a binary sequence $\begin{matrix} b = (b_{i} | i \in N) \in {0, 1}^{ω} \end{matrix}$ such that $x (b) = x$ . For each $a \in {0, 1}$ , define the binary sequence $\begin{matrix} b^{(a)} = (b_{i}^{(a)} | i \in N) \in {0, 1}^{ω} \end{matrix}$ by $\begin{matrix} b_{i}^{(a)} = \{\begin{array}{ll} b_{i} & if i \in J_{a} \\ 0 & if i \in J_{1 - a} \end{array} \end{matrix}$ for all $i \in N$ , and let $x_{a} = x (b^{(a)})$ . Then $x_{0}, x_{1} \in C_{0}$ and $x_{0} + x_{1} = x$ , confirming that $span (C_{0}) = R$ .

In summary, for each $s \in [0, 1]$ , we have by known methods a set $C_{s} \subseteq [0, 1]$ with the following three properties.

${dim}_{H} (C_{s}) = s$ .

For all oracles $A \subseteq N$ that compute s, the set $\begin{matrix} D^{A} = {x \in C_{s} | {dim}^{A} (x) = s} \end{matrix}$ has the cardinality of the continuum.

$span (C_{s}) = R$ .

3. Dimensions of Hamel bases

In this section we prove our main theorem, which is the following.

Theorem 1.
For every $s \in [0, 1]$ there is a Hamel basis B of $R$ over $Q$ such that ${dim}_{H} (B) = s$ .
Proof.
Let $s \in [0, 1]$ , and define the set $C_{s}$ as in Section 2. Let $\begin{matrix} (x_{α} | α < 2^{ℵ_{0}}) \end{matrix}$ be a wellordering of $C_{s}$ , and let $\begin{matrix} ((A_{β}, y_{β}) | β < 2^{ℵ_{0}}) \end{matrix}$ be a wellordering of the set $\begin{matrix} D = {(A, y) \in P (N) \times C_{s} | s ⩽_{T} A and {dim}^{A} (y) = s} . \end{matrix}$ Define the sequence $\begin{matrix} (u_{γ} | γ < 2^{ℵ_{0}}) \end{matrix}$ of real numbers by the following transfinite recursion. Given $γ < 2^{ℵ_{0}}$ , let $B_{γ} = {u_{δ} | δ < γ}$ . Write $γ = ξ + k$ , where ξ is 0 or a limit ordinal and $k \in N$ . Call γ even or odd if k is even or odd, respectively.
If $γ = ξ + 2 k$ is even, let $\begin{matrix} u_{γ} = y_{β}, \end{matrix}$ where β is the least ordinal such that $A_{β} = A_{ξ + k}$ and $y_{β} \notin span (B_{γ})$ .

If γ is odd, let $\begin{matrix} u_{γ} = x_{α} \end{matrix}$ be the first element of $C_{s} ∖ span (B_{γ})$ .

To see that this recursion is well defined, let $γ < 2^{ℵ_{0}}$ . Then $| B_{γ} | < 2^{ℵ_{0}}$ , so $| span (B_{γ}) | < 2^{ℵ_{0}}$ . Since $| D | = | C_{s} | = 2^{ℵ_{0}}$ , it follows that $u_{γ}$ exists.

Let $\begin{matrix} B = {u_{γ} | γ < 2^{ℵ_{0}}} . \end{matrix}$ The rest of this proof establishes that B is a Hamel basis of $R$ over $Q$ and that ${dim}_{H} (B) = s$ .

We first show that $span (B) = R$ . For this, since we saw in Section 2 that $span (C_{s}) = R$ , it suffices to show that $C_{s} \subseteq span (B)$ , i.e., that the set $E = C_{s} ∖ span (B)$ is empty. To this end, let x be a lower bound of E in our wellordering of $C_{s}$ . That is, let $x = x_{α}$ , where $α < 2^{ℵ_{0}}$ and $x_{α^{'}} \in span (B)$ holds for all $α^{'} < α$ . Since $α < 2^{ℵ_{0}} = | B |$ and only finitely many elements of B are required to put each $α^{'}$ into $span (B)$ , it follows that there exists $γ < 2^{ℵ_{0}}$ such that $\begin{matrix} {x_{α^{'}} | α^{'} < α} \subseteq span (B_{γ}) . \end{matrix}$ Moreover, we can insist here that γ be odd. Then either $x \in span (B_{γ})$ or $u_{γ} = x_{α} = x$ , so $x \in B$ . Either way, $x \in span (B)$ , so $x \notin E$ . We have now shown that no lower bound of E is an element of E, i.e., that E has no least element in our wellordering. This implies that $E = \emptyset$ , completing our proof that $span (B) = R$ .

Since our construction ensures that $u_{γ} \notin span (B_{γ})$ holds for all $γ < 2^{ℵ_{0}}$ , we now have that B is a Hamel basis of $R$ over $Q$ .

We finish this proof by showing that ${dim}_{H} (B) = s$ . It is clear that ${dim}_{H} (B) ⩽ s$ , since $B \subseteq C_{s}$ and ${dim}_{H} (C_{s}) = s$ . Hence it suffices to show that $\begin{matrix} s \in (0, 1] \Rightarrow {dim}_{H} (B) ⩾ s . \end{matrix}$ For this, assume that $s \in (0, 1]$ , and let $A \subseteq N$ be an oracle such that $s ⩽_{T} A$ . We saw in Section 2 that the set $\begin{matrix} D^{A} = {y \in C_{s} | {dim}^{A} (y) = s} \end{matrix}$ has the cardinality of the continuum, so there exist ordinals γ and β such that $A_{β} = A$ and $y_{β} = u_{γ} \in B$ . This implies that ${dim}^{A} (u_{γ}) = s$ . Writing $u (A) = u_{γ}$ here, it follows by the Point-to-Set principle (together with the obvious fact that ${dim}^{C} (x) ⩽ {dim}^{D} (x)$ holds whenever $D ⩽_{T} C$ ) that $\begin{aligned} {dim}_{H} (B) & = min_{A \subseteq N} sup_{u \in B} {dim}^{A} (u) \\ = min_{\begin{array}{c} A \subseteq N \\ s ⩽_{T} A \end{array}} sup_{u \in B} {dim}^{A} (u) \\ ⩾ min_{\begin{array}{c} A \subseteq N \\ s ⩽_{T} A \end{array}} {dim}^{A} (u (A)) \\ = s . \end{aligned}$ □

4. Conclusion

Orponen [20] has already found classical proofs of two projection theorems of N. Lutz and Stull [16] that were first proven via the Point-to-Set Principle, and he generalized these theorems in the process. We conjecture that our theorem on Hamel bases also admits a classical proof. More generally, we look forward to a better understanding of the power and limitations of computability-theoretic methods for discovering proofs of new theorems in classical mathematics.

Footnotes

Acknowledgement

We thank two anonymous referees for useful suggestions.

References

T.M.

Apostol, Calculus, Volume II: Multi-Variable Calculus and Linear Algebra, with Applications to Differential Equations and Probability, John Wiley & Sons, 1969.

Blass, Existence of bases implies the axiom of choice, Contemporary Mathematics 31 (1984).

Cabrelli,

K.E.

Hare and

Molter, Sums of Cantor sets yielding an interval, Journal of the Australian Mathematical Society 73 (2002), 405–418, https://api.semanticscholar.org/CorpusID:11396262 . doi:10.1017/S1446788700009058.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Springer Science & Business Media, 2010.

P.R.

Halmos, Finite-Dimensional Vector Spaces, Dover, 2017.

P.R.

Halmos, Naive Set Theory, Dover, 2017.

Hamel, Eine Basis aller Zahlen und die unstetigen Lösungen der Funktionalgleichung:

f (x + y) = f (x) + f (y)

, Mathematische Annalen 60(3) (1905), 459–462. doi:10.1007/BF01457624.

F.B.

Jones, Measure and other properties of a Hamel basis, Bulletin of the American Mathematical Society 48(6) (1942), 472–481. doi:10.1090/S0002-9904-1942-07710-X.

Li and

P.M.B.

Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 4th edn, Springer Publishing Company, Incorporated, 2019. ISBN 3030112977.

10.

J.H.

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

11.

J.H.

Lutz and

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

12.

J.H.

Lutz and

Lutz, Who asked us? How the theory of computing answers questions about analysis, in: Complexity and Approximation, Springer, 2020, pp. 48–56. doi:10.1007/978-3-030-41672-0_4.

13.

J.H.

Lutz and

Mayordomo, Dimensions of points in self-similar fractals, SIAM Journal on Computing 38(3) (2008), 1080–1112. doi:10.1137/070684689.

14.

J.H.

Lutz and

Mayordomo, Algorithmic fractal dimensions in geometric measure theory, in: Handbook of Computability and Complexity in Analysis, Springer, 2021, pp. 271–302.

15.

Lutz, Fractal intersections and products via algorithmic dimension, ACM Trans. Comput. Theory 13(3) (2021), 14:1–14:15. doi:10.1145/3460948.

16.

Lutz and

D.M.

Stull, Projection theorems using effective dimension, in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, 2018.

17.

Lutz and

D.M.

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

18.

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

19.

Moschovakis, Notes on Set Theory, Springer, 2005.

20.

Orponen, Combinatorial proofs of two theorems of Lutz and Stull, in: Mathematical Proceedings of the Cambridge Philosophical Society, Cambridge University Press, 2021, pp. 1–12.

21.

Roitman, Introduction to Modern Set Theory, John Wiley & Sons, 1990.

22.

Shen,

V.A.

Uspensky and

Vereshchagin, Kolmogorov Complexity and Algorithmic Randomness, Vol. 220, American Mathematical Soc., 2017.

23.

Sierpiński, Sur la question de la mesurabilité de la base de M. Hamel, Fundamenta Mathematicae 1(1) (1920), 105–111. doi:10.4064/fm-1-1-105-111.

24.

T.A.

Slaman, On capacitability for co-analytic sets, New Zealand J. Math. 52 (2021), 865–869. doi:10.1007/s13226-021-00101-z.

25.

D.M.

Stull, Optimal oracles for Point-To-Set Principles, in: 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, Marseille, France, March 15–18, 2022,

Berenbrink and

Monmege, eds, LIPIcs, Vol. 219, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 57:1–57:17. Virtual Conference. doi:10.4230/LIPIcs.STACS.2022.57.

26.

D.M.

Stull, Pinned distance sets using effective dimension, 2022, CoRR arXiv:2207.12501. doi:10.48550/arXiv.2207.12501.

27.

Zermelo, Untersuchungen über die Grundlagen der Mengenlehre. I, Mathematische Annalen 65(2) (1908), 261–281. doi:10.1007/BF01449999.

The Point-to-Set Principle and the dimensions of Hamel bases

Abstract

Keywords

1. Introduction

1 In 1984, confirming a 1908 conjecture of Zermelo [27], Blass [2] proved that the existence of bases for all vector spaces implies the axiom of choice.

3. Dimensions of Hamel bases

Footnotes

Acknowledgement

References

¹
In 1984, confirming a 1908 conjecture of Zermelo [27], Blass [2] proved that the existence of bases for all vector spaces implies the axiom of choice.