# Matryoshka Sequences

A Matryoshka sequence is a combination of a function $f:\{1,2,\dots,m-1\}\to \mathbb{C}$ and a complex number $\epsilon$. To wit, set

$F(x):=f(x \bmod m)$ if $x$ is not a multiple of $m$, and
$F(x) := \epsilon F(x/m)$ if $x$ is a multiple of $m$.

## Examples

### Walters' example $\lambda_3$

The most straightforward example is $\lambda_3$, the multiplicative sequence sending primes to 1 or -1 according to whether they are congruent to 1 or -1 modulo 3, and sending 3 to 1. This is the Matryoshka sequence from $m=3, f(1)=-f(2)=1,\epsilon = 1$. We have the pleasant formula:

$\sum_{j=1}^k \lambda_3(jd) = \lambda(d) \sum_{j=1}^k \lambda_3(j) = \lambda_3(d) S(k),$

where $S(k)$ is the number of 1's in the ternary expansion of k. The discrepancy therefore satisfies

$\delta(N,\lambda_3) \leq \log_3(2N+1) \lt \log_3(N)+1$

with equality infinitely often.

### Legendre symbol $\lambda_p$

See paper of Borwein, et al.

### Improved Walters $\mu_3$

Define $\mu_3$ by taking $\displaystyle m=3, f(1)=-f(2)=1, \epsilon = -1$. This function is multiplicative. We have the pleasant formula:

$\sum_{j=1}^k \mu_3(jd) = \mu_3(d) \sum_{j=1}^k \mu_3(j) = \mu_3(d) S(k)$

where $S(k)$ is the number of 1's in the ternary expansion of $k$ in even position, minus the number of 1's in odd position. The discrepancy therefore satisfies

$\delta(N,\mu_3) \leq \log_9(8N+1) \lt \log_9(N) + 1$

with equality infinitely often.

### Generalized Walters $\mu_p$

Fix an odd prime $p$, and let $\displaystyle \omega=\exp(2\pi i /(p-1))$. Then $\mu_p$ is the Matryoshka sequence from $\displaystyle m=p,f(j)=\omega^{j-1}, \epsilon=\omega$. This coincides with the Improved Walters for $p=3$, but is not multiplicative for $p\gt3$. We have the pleasant formula

$\sum_{j=1}^k \mu_p(j) = \sum_{r=0}^{\ell} \omega^r \sum_{j=1}^{b_r} \omega^{j-1}$

where $k= b_0+b_1 p + b_2 p^2 + \dots+b_{\ell}p^{\ell}$ (all of the $b_r$ are in $\{0,1,\dots,p-1\}$, and $\ell=\lfloor \log_p k \rfloor$). We can rewrite the above sum as

$\sum_{r=0}^{\ell} \omega^r \sum_{j=1}^{b_r} \omega^{j-1} = \sum_{s=0}^{\ell'} \sum_{r=0}^{p-2} \omega^r \sum_{j=1}^{b_{r+s(p-1)}} \omega^{j-1},$

with $\ell' = \lfloor \log_{p^{p-1}}k \rfloor$. Set $M_p$ to be the maximum of $\left|\sum_{r=0}^{p-2} \omega^r \sum_{j=1}^{\beta_r} \omega^{j-1}\right|$ where $\beta_r$ is in $\{0,1,\dots,p-1\}$. We now have

$\left| \sum_{j=1}^k \mu_p(j) \right| \leq (1+\log_{p^{p-1}}k) M_p$,

so what is $M_p$? As in the comments in this thread, $M_p \gtrsim c p^2$, so that the discrepancy

$\delta(N,\mu_p) \geq \frac{cp^2}{(p-1)\log(p)} \log N.$

## Formulas to assist in the handling of Matryoshka sequences

Let $m'=m/\gcd(d,m), M = \lfloor k/m' \rfloor m'$. Then

$\sum_{i=1}^k F(id) = \sum_{i=1}^{k-M} f(id \bmod m) + \sum_{i=1}^{\lfloor k/m' \rfloor} F(i d/ \gcd(d,m))$

## Source code

Mathematica code for generating the terms of $\mu_p(k)$.

   \[Mu][p_, k_] := \[Mu][p, k] =
Block[{\[Omega] = Exp[2 \[Pi] I / (p - 1)]},
Which[1 <= k < p, \[Omega]^(k - 1),
Mod[k, p] == 0, \[Omega] \[Mu][k/p] ,
True, \[Mu][Mod[k, p, 1]]]];


Mathematica code for $\sum_{i=j}^k \mu_p(j)$.

    SumFormulaForMu[p_,k_]:=
Module[
{j,bj,bseq},
j=IntegerExponent[k,p];
bj=Mod[k/p^j,p];
bseq=Reverse[IntegerDigits[k,p]];
Table[\[Omega]^r,{r,0,Length[bseq]-1}].(Sum[\[Omega]^(j-1),{j,1,#}]&/@bseq)]
`