4
$\begingroup$

For real irrational $C > 1 $ and natural $n,b$, define $a(C,n,b)=\lfloor C^n \rfloor \mod b$

Q1 For which $C,b$ is $a(C,n,b)$ computable in time polynomial in $\log{n}$?

Searching in OEIS suggests that for $C \in \{1+\sqrt{2},1+\sqrt{3},(1+\sqrt{5})/2\}$, $a(C,n,b)$ satisfy linear recurrence with constant coefficients and so it is efficiently computable over the integers and all bases $b$.

In OEIS: a(n) = floor(phi^n)

a(n) = floor((1+sqrt(2))^n)

a(n) = floor((1+sqrt(3))^n)

For natural $k$, $a(b^{1/k},n,b)$ is related to the base $b$ representation of $b^{1/k}$ so it is probably hopeless.

Q2 Is $a(1+\sqrt{6},n,b)$ efficiently computable in some base $b$?

(We couldn't find linear recurrence for it)

Q3 Except linear recurrences, are there other islands of tractability for algebraic $C$?

In comments @user44191 asked about specific constant near $1.75$.

We couldn't find linear recurrence, but got degree 2 relation factoring into linear factors, which might be hint:

0 == (2*a(n + 2) - 3*a(n + 1) - 3*a(n - 1) - a(n - 3) + a(n) - 2) *
         (a(n + 1) - a(n - 1) - a(n - 3) - a(n) - 1)

Computational bugs are possible.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ For algebraic $\alpha$ such that $|\alpha| > 1, |\alpha'| < 1$ for all conjugates $\alpha'$, I suspect it should be easily computable; this is true for the examples given. $\endgroup$
    – user44191
    Commented Mar 7, 2020 at 17:59
  • 1
    $\begingroup$ I should note that I assumed $\alpha$ is an algebraic integer. The above may be somewhat overly general; a sufficient restriction is that there is a unique conjugate of second-largest magnitude (which, necessarily, will be real). In that case, there will be a clear linear recurrence. It may still be possible to get a linear recurrence otherwise; I don't have any examples with 2 roots of the 2nd largest magnitude off the top of my head, but it might be worth investigating those. $\endgroup$
    – user44191
    Commented Mar 7, 2020 at 19:18
  • 1
    $\begingroup$ An example to test: the unique positive root of $x^3 - 2x^2 + x - 1$; I think that computing $\lfloor C^n \rfloor$ is equivalent to determining whether $n \text{arg}(\alpha')$ has positive cosine, where $\alpha'$ is either nonpositive root. $\endgroup$
    – user44191
    Commented Mar 7, 2020 at 21:30
  • $\begingroup$ @user44191 I edited with partial results about the test. $\endgroup$
    – joro
    Commented Mar 8, 2020 at 8:04
  • $\begingroup$ For the $\alpha$ I wrote above, there is a degree 6 relation that use only 4 terms that's true for sufficiently large $n$: if $b(n) = a(n + 3) - 2 a(n + 2) + a(n + 1) - a(n)$, then $\prod_{i = -2}^3 (b(n) - i) = 0$. This is because $b(n)$ is an integer and because $a(n) - \alpha^n$ is either very close to $0$ or very close to $-1$. $\endgroup$
    – user44191
    Commented Mar 8, 2020 at 12:13

0

Reset to default

You must log in to answer this question.