2
$\begingroup$

Hofstadter's Q sequence is defined by $Q(1) = Q(2) = 1$ and $Q(n) = Q(n-Q(n-1)) + Q(n-Q(n-2))$ for $n \geq 3$. So far hardly anything on this sequence has been proved -- not even that $Q(n)$ is well-defined for all positive integers $n$.

Put $a := \frac{1}{4}(9 - \sqrt{89})$, and let $$ f: \mathbb{R} \rightarrow \mathbb{R}, \ \ x \mapsto \begin{cases} ax^3 + \left(\frac{1}{2} - 6a\right)x^2 + \left(11a-\frac{3}{2}\right)x + 2 - 6a & \text{if} \ x \leq 3, \\\ f(x-f(x-1)) + f(x-f(x-2)) & \text{if} \ x > 3. \\\ \end{cases} $$ Then by choice of the polynomial for $x \leq 3$, the function $f$ is well-defined (note that we have $f(x) > 0$ for any $x \in \mathbb{R}$), continuous and differentiable at all $x \in \mathbb{R}$, and we have $f(n) = Q(n)$ for any positive integer $n$ for which $Q(n)$ is well-defined. Also, by construction for $x \geq 3$ the function~$f$ satisfies the functional equation $f(x) = f(x-f(x-1)) + f(x-f(x-2))$ (but obviously it does not do so for $x < 3$).

Questions:

  • What can be said about the function $f$ besides these basic facts?

  • Does the functional equation $f(x) = f(x-f(x-1)) + f(x-f(x-2))$ have continuous and differentiable (or at least continuous) solutions $f: \mathbb{R} \rightarrow \mathbb{R}$ other than the zero function?

  • Or to be a bit more bold: does it have solutions $f: \mathbb{C} \rightarrow \mathbb{C}$ other than the zero function which are meromorphic on the complex plane?

Remarks: The graph of the function $f$ for $-1 \leq x \leq 15$ looks as follows (the graph of the polynomial used to define $f$ for $x \leq 3$ is shown in red):

Graph of f

The graph for $-1 \leq x \leq 23$ looks as follows:

Graph of f

A plot of the first 576 terms of Hofstadter's Q sequence looks like this:

Plot of Hofstadter's Q sequence

$\endgroup$
6
  • $\begingroup$ Presumably you mean $f(x) = f(x−f(x−1))+f(x−f(x−2))$? The formula "$f(x−f(x−1))+f(x−f(x−2))$" itself is not a functional equation. $\endgroup$ Commented Jun 20, 2013 at 16:39
  • $\begingroup$ Nice pictures. Suppose instead of your polynomial you use a straightline approximation: choice 1 is f=1 for (0,2] and (x-1) for [2,3], while choice 2 is f=x on (0,1) and otherwise looks like choice 1. Can you comment on the results for either of these choices? Gerhard "Maybe Make Pretty Graphs Too?" Paseman, 2013.06.20 $\endgroup$ Commented Jun 20, 2013 at 16:46
  • $\begingroup$ @Noam: Of course. -- Thanks for spotting the typo. $\endgroup$
    – Stefan Kohl
    Commented Jun 20, 2013 at 19:27
  • $\begingroup$ @Gerhard: A straightline approximation won't do -- you won't get a function which is continuous and differentiable at $x=3$. Making the function differentiable at $x=3$ requires the 'complicated' polynomial. $\endgroup$
    – Stefan Kohl
    Commented Jun 20, 2013 at 19:33
  • $\begingroup$ Yes, but until one gets to the word "meromorphic" in your post, there is no hint that differentiability is a concern of yours. I thought your issue would be whether it results in a total function on the reals greater than or equal to 1. In any case, it would be of interest to see if the function needs to be defined on (0,1) in the straightline version for the functional part of the definition to work. Gerhard "With Sides Reversed Is Not" Paseman, 2013.06.20 $\endgroup$ Commented Jun 21, 2013 at 1:47

0

You must log in to answer this question.