Sandbox:DavidKohler/Relativized Alon Conjecture/Ramanujan (function)

Definition

A function ƒ(k) on positive integers is d-Ramanujan of order α if there exists a polynomial p and a positive constant c such that

$\displaystyle |f(k)-(d-1)^{k}p(k)|\leq ck^{c}a^{k}\quad \forall k\geq 1$

We call (d-1)^kp(k) the principal term of the function and ƒ(k)-(d-1)^kp(k) its error term.

A d-Ramanujan function of order √d-1 is simply called a d-Ramanujan function.

Properties

Ramanujan functions are closed under addition and convolution. More precisely, let ƒ₁ and ƒ₂ be two d-Ramanujan functions of order α then

• ƒ₁ + ƒ₂ is d-Ramanujan of order α

Proof

Assume that ${\begin{aligned}f_{1}(k)&=(d-1)^{k}p_{1}(k)+e_{1}(k),\quad |e_{1}(k)|\leq c_{1}k^{c_{1}}\alpha ^{k}\\f_{2}(k)&=(d-1)^{k}p_{2}(k)+e_{2}(k),\quad |e_{2}(k)|\leq c_{2}k^{c_{2}}\alpha ^{k}\quad \forall k\geq 1\end{aligned}}$ then clearly ${\begin{aligned}|(f_{1}+f_{2})(k)-(d-1)^{k}(p_{1}+p_{2})(k)|&=|e_{1}(k)+e_{2}(k)|\\&\leq |e_{1}(k)|+|e_{2}(k)|\\&\leq 2ck^{c}\alpha ^{k}\quad \forall k\geq 1\end{aligned}}$ where c is the largest of the constants c1 and c2.

• ƒ₁ * ƒ₂ is d-Ramanujan of order α

Proof
First, recall the definition of the convolution of two functions: $\displaystyle (f_{1}*f_{2})(k)=\sum _{j=1}^{k-1}f_{1}(j)f_{2}(k-j)$ Assuming that ${\begin{aligned}f_{1}(k)&=(d-1)^{k}p_{1}(k)+e_{1}(k),\quad |e_{1}(k)|\leq c_{1}k^{c_{1}}\alpha ^{k}\\f_{2}(k)&=(d-1)^{k}p_{2}(k)+e_{2}(k),\quad |e_{2}(k)|\leq c_{2}k^{c_{2}}\alpha ^{k}\quad \forall k\geq 1\end{aligned}}$ TO CONTINUE

To do
	Continue the above proof