what are notable/ prominent inductive proofs relating to fractals?

the motivation for this question is:

  • fractals are very difficult mathematical objects to work with, and many problems/questions about them lie at the boundary of decidable/undecidable (and many are undecidable).
  • so it would be useful to study proofs that somehow cleverly/ surprisingly/ successfully "tame" this complexity.
  • also, presumably number theory could play a role here, eg a number-theoretic property that has a proof and has also been considered by some to be "fractal" under misc interpretations.
  • many famous open problems eg in number theory seem to have a fractal nature and that possibly substantially accounts for their difficulty eg Collatz visualizations/ tiles & Collatz fractal
  • (am acknowledging beforehand there is not a strict/widely agreed definition of fractal.)

somewhat related to Excellent uses of induction and recursion

  • Many questions about fractals are undecidable? What are examples? – Douglas Zare Feb 11 '17 at 2:01
up vote 2 down vote accepted

Spectral decimation is an inductive process where the eigenvalues of a natural Laplacian on "nice" fractals is computed inductively. The idea is that by using a sequence of finite graphs to approximate the graph and graph Laplacians on these graphs one can inductively determine the eigenvalues of the Laplacian on the n+1'st graph from those of the n'th graph. Ultimately the spectrum of the limit Laplacian is the closure of the scaling limit of the spectra on the finite graphs. The original reference for this is Fukushima and Shima "On a spectral analysis for the Sierpiński gasket" from 1992. MathSciNet or the direct link to the journal is Springer Pay-wall. (Apologies to those who do not have access to MathSciNet).

I am not sure which side of the induction versus iteration divide this lands for you. (Edit: By this divide I am thinking about something like iteratively constructing a fractal level by level but then proving that something is true at all levels. At some point in this process we went from doing something iteratively to doing something inductively. I am not certain that Spectral decimation is a pure enough form of induction for what the OP is asking.) Certainly much of the emphasis on self-similar fractals is an attempt to be able to call upon iterative methods at the very least and in many cases these proofs do become inductive. There is another proof that I am thinking of that occurs in proving Harnack inequalities for harmonic functions on the Sierpinski carpet, but that is for another answer.

The local definition of "nice" for this answer is either post-critically finite fractals or finitely ramified with a doubly transitive symmetry group fractals.

  • sounds highly relevant, but not sure what you mean by "induction vs iteration divide". re the ref can you cite it beside the url, & anyway that url is apparently a search url, another one would be better – vzn Apr 15 '14 at 19:03
  • Fixed the links and added a longer description of what I was trying to say with the induction vs. iteration divide. Hope that helps. – BSteinhurst Apr 15 '14 at 19:11
  • ok thx... but what did it prove? are you saying the goal was to derive the spectrum of the limit Laplacian of the Sierpinski gasket? – vzn Apr 15 '14 at 20:20
  • That paper showed what the spectrum is. Incidentally the proof for the spectrum actually can be used to also prove the limit Laplacian also exists. But that is an older result than this paper. – BSteinhurst Apr 15 '14 at 20:39

As I have shown in this answer and this answer, the Laver tables (see also this chapter) contain fractal structure which resembles the Sierpinski triangle (see also this link). In fact, all of the combinatorial structure of the classical Laver tables is contained in their corresponding fractals. Induction is one of the main techniques of proving facts about Laver tables and generalizations thereof.

$\textbf{Example 1:}$ One shows that the operation $*_{n}$ on $\{1,...,2^{n}\}^{2}$ is well-defined and total by defining $x*_{n}y$ by a double induction which is descending on $x$ and for all $x$ the induction is ascending on $y$. The descending-ascending double induction is used commonly to prove facts about the Laver tables.

$\textbf{Example 2:}$ In order to prove that $*_{n}$ is self-distributive, one proceeds by induction on $n$. For each $n$ one proves that $x*_{n}(y*_{n}z)=(x*_{n}y)*_{n}(x*_{n}z)$ using a triple induction which is descending on $x$ and for each $x$ the induction is descending on $y$ and for each $y$ the induction is ascending on $z$.

$\textbf{Example 3:}$ Randall Dougherty uses induction to prove every lemma and result in this paper. In this paper, Dougherty shows that if $f(n)$ is the least natural number where $o_{f(n)}(1)\geq n$, then $f$ grows faster than the Ackermann function. The results in this paper are proven purely algebraically without necessarily resorting to large cardinals.

$\textbf{Transfinite induction:}$ Finally, since the Laver tables arise from the the algebras of elementary embeddings, one can use transfinite induction on large cardinals to prove results about finite algebras which do not have any known proofs without large cardinal hypotheses. However, since $\mathcal{E}_{\lambda}^{+}\neq\emptyset$ implies that $\text{cf}(\lambda)=\omega$ and by this answer, this sort of transfinite induction more closely resembles induction on $\mathbb{N}$ rather than the typical cases of transfinite induction.

Transfinite induction can be used to construct a linear ordering of elementary embeddings, and that linear ordering produces a compatible linear ordering on some finite algebras resembling the Laver tables.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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