Suppose $K$ is a subset of $[0,1]$ with the following property: for almost $x,y \in K$, we have

$$\frac{x+y}{2} \not\in K.$$

(Here, "almost in $K$" means "in $K$ except for a countable subset").

Such a set must have holes, and the Cantor tridiagonal set has this property. What can we say about the Hausdorff dimension of $K$? Is it true that it is less than $\ln 2 / \ln 3$?

Can we even say that the Hausdorff measure $H^{\ln 2/ \ln 3}(K)$ is finite?


We can find Cantor-like sets of Hausdorff dimension arbitrarily close to $1$ which satisfy your property.

Lemma: If a subset $S \subseteq \{1, 2, \dots, n\}$ of cardinality $|S| = m$ has no length-$3$ arithmetic progressions, then we can find a subset $K \subsetneq [0, 1]$ with a Hausdorff dimension of:

$$ \dfrac{\log{m}}{\log(2n-1)} $$

In particular, the Cantor ternary set is the special case of applying this construction to $S = \{1, 2\}$.

Proof: We apply a Cantor-like construction, replacing the interval $K_0 = [0, 1]$ with $m$ intervals:

$$ K_1 = \bigcup \{ [\dfrac{2s-2}{2n-1}, \dfrac{2s-1}{2n-1}] : s \in S \} $$

and iterating in the obvious way to produce a sequence $K_0 \supsetneq K_1 \supsetneq K_2 \supsetneq \dots$. Define $K$ to be the limit (intersection) of these sets.

Now given any two points $x, y \in K$, we consider the first iteration $K_n$ of the process which puts $x,y$ in different intervals. Then I claim that $\frac{x+y}{2}$ is not in $K_n$.

Due to the recursive structure of $K$, we can wlog assume $n = 1$. Hence we just need to show that if $x$ and $y$ belong to different intervals in $K_1$, their mean does not belong to $K_1$. This is where we make use of the $3AP$-less-ness of $S$.

For simplicity of notation, we'll scale $K_1$ up by $2n - 1$ and suppose that:

$$ x \in [2s - 2, 2s - 1], y \in [2t - 2, 2t - 1] $$

where $s,t \in S$ and wlog $s < t$.

Then the mean of $x$ and $y$ must consequently satisfy:

$$ \dfrac{x + y}{2} \in [s + t - 2, s + t - 1] $$

If $s + t$ is odd, this interval doesn't belong to $K_1$ by parity. If $s + t$ is even, then this interval doesn't belong to $K_1$ because $\frac{1}{2}(s + t) \notin S$ by the $3AP$-less-ness of $S$.

The result follows.

Theorem: For every $\varepsilon > 0$, we can find a set $K$ of Hausdorff dimension greater than $1 - \varepsilon$

Proof: By Lemma 1, we just need to find a $m$-subset of $[n]$ with no three-term arithmetic progression and which satisfies:

$$ \dfrac{\log{m}}{\log(2n-1)} > 1 - \varepsilon$$

or equivalently:

$$ \dfrac{\log(\frac{m}{2n - 1})}{\log(2n - 1)} > -\varepsilon$$

or equivalently:

$$ \dfrac{m}{2n - 1} > (2n - 1)^{-\varepsilon} $$

It is thus sufficient to find a $3AP$-less set with density $\delta := \dfrac{m}{n}$ satisfying:

$$ \delta \geq 2(2n - 1)^{-\varepsilon} $$

Such large $3AP$-less sets exist. See Theorem 3.1 (Behrend, 1946) of the following paper:


QED #ReductionToAKnownProblem

  • $\begingroup$ Your answer doesn't seem to address the possibility that $x$ has some digits dominating those of $y$ and other digits with the reverse ordering. $\endgroup$ – Anthony Quas Aug 8 '15 at 18:20
  • $\begingroup$ @AnthonyQuas It certainly does -- that was the reason for including an empty interval between each pair of possibly-non-empty intervals in $K_1$. Note that we only consider the first 'digit' in which $x$ and $y$ differ, and treat the remaining 'digits' as an arbitrary real in $[0, 1]$. $\endgroup$ – Adam P. Goucher Aug 8 '15 at 19:02
  • $\begingroup$ OK - fair enough... $\endgroup$ – Anthony Quas Aug 8 '15 at 20:23

In Construction of 1-dimensional subsets of the reals not containing similar copies of given patterns Tamás Keleti constructs a compact set of Hausdorff dimension $1$ which contains no similar copy of any out a given countable number of $3$-element sets. In particular, there is a compact set of Hausdorff dimension $1$ which does not contain any arithmetic progressions.

His construction does not use Behrend's example at all, and it is intrinsic to the reals as it depends on a multi-scale argument, so it is substantially different from Adam Goucher's nice solution.

On the other hand, an easy application of the Lebesgue density theorem shows that any set of positive Lebesgue measure contains an arithmetic progression of length $3$ (and of any finite length).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.