User garoudan - MathOverflow

Summing a function using modulus.

2011-11-28T12:16:53Z

The problem:

If the infinite sum of a function is known, how to find:

$$\begin{align*} \sum_{i\equiv 0 \mod m}f(x_0+i)=\\ f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m)+\ldots \end{align*}$$

And if the finite sum of a function is known, how to find:

$$\begin{align*} \sum_{i\equiv 0 \mod m}^{i = {(x_0+\lfloor \frac{x-x_0+1}{m}\rfloor m)}}f(x_0+i)=\\ f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m) &\quad +\ldots+f\left(x_0+\left\lfloor \frac{x-x_0+1}{m}\right\rfloor m\right) \end{align*}$$

Details:

I had posted this question in Math.StackExchange too (about one day before). It's in this link.

If we know a function $f$ and we can find the sum of its terms (defined as $S_f$), how to find the sum, but jumping some factors (defined as $MS_f$, where M representes modular)?

What's the relation with the sum function ($S_f$)? (I think this uses the root of the unity, but don't know how.)

For example, if:

$$S_f=\displaystyle\sum_{i=1}^{\infty}f(i)=f(1)+f(2)+\ldots$$

with infinite terms, how to find

$$\begin{align*} MS_f(x_0,m)&=\sum_{i\equiv 0 \mod m}f(x_0+i)\\ & = f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m)+\ldots \end{align*}$$

And if:

$$S_f(x)=\displaystyle\sum_{i=1}^{x}f(i)=f(1)+\ldots+f(x-1)+f(x),$$

how to find

$$\begin{align*} MS_f(x,x_0,m)&=\sum_{i\equiv 0 \mod m}^{i = {(x_0+\lfloor \frac{x-x_0+1}{m}\rfloor m)}}f(x_0+i)\\ & = f(x_0)+f(x_0+m)+f(x_0+2m)+f(x_0+3m) \\ &\quad +\ldots+f\left(x_0+\left\lfloor \frac{x-x_0+1}{m}\right\rfloor m\right) \end{align*}$$

where $(x_0+\lfloor \frac{x-x_0+1}{m}\rfloor m)$ is the ultimate term of the arithmetic progression $x_0+k\times m$ which not exceeds $x$.

Edited:

As Jacques Carette said, I think the answer is using something like:

$MS_f(x,x_0,m)=\displaystyle\sum_{i=0}^{m-1}a_iS_f(w^ix)$ or $\displaystyle\sum_{i=0}^{m-1}a_iS_f(w^i(x+x0))$

but I don't know exactly.

Example:

$$S_f=\sum_{i=1}^{\infty}\frac{x^{i-1}}{(i-1)!}=e^x, \quad f(i)=\frac{x^{i-1}}{(i-1)!}$$ $$\begin{align*} MS_f(x_0,m)=\sum_{i\equiv 0 \mod m}f(x_0+i)=\sum_{i\equiv 0 \mod m}\frac{x^{(x_0+i)-1}}{((x_0+i)-1)!}\implies\\ MS_f(3,2)=\sum_{i\equiv 0 \mod 2}\frac{x^{(3+i)-1}}{((3+i)-1)!}=\sum_{j=0}^{\infty}\frac{x^{3+2j-1}}{(3+2j-1)!}=\cosh (x)-1 \end{align*}$$

How to find the sum?

2011-11-15T01:27:41Z

The problem:

How to find this sum?

$$\sum_{a=0}^{\infty}\frac{1}{(\frac{(a(p-1)+b)!}{p^{q_a}} \mod p) \times p^q}$$

where:

$p \in Primes$

$b \in \mathbb{N}\quad$, $0 \leq b \leq p-2$, but not defined.

$q_a$ is the greatest power of $p$ who divides the term $(a(p-1)+b)!$

Details:

$b$ refers to the congruence modulus $p-1$, so $0 \leq b \leq p-2$.

$a(p-1)+b$ for differents $a$'s and $b$'s we can express all natural numbers,

so the summation looks like the sequence of $e$ but a bit modified.

$q_a$ can also be expressed as: $q_a=\lfloor{\frac{(a(p-1)+b)}{p}}\rfloor+\lfloor{\frac{(a(p-1)+b)}{p^2}}\rfloor+\lfloor{\frac{(a(p-1)+b)}{p^3}}\rfloor+\ldots$

$\frac{(a(p-1)+b)!}{p^{q_a}} \bmod p$ is just the remainder of the division by $p$.

Expandind the sum we have:

$\frac{1}{(\frac{b!}{p^{q_0}} \mod p)p^{q_0}}+\frac{1}{(\frac{(p-1+b)!}{p^{q_1}} \mod p)p^{q_1}}+\frac{1}{(\frac{(2p-2+b)!}{p^{q_2}} \mod p)p^{q_2}}+\frac{1}{(\frac{(3p-3+b)!}{p^{q_3}} \mod p)p^{q_3}}+\ldots$

just to clarify, to $p=2$ and $b=0$ we have:

$\frac{1}{(0! \mod 2)2^0}+\frac{1}{(1! \mod 2)2^0}+\frac{1}{(\frac{2!}{2^1} \mod 2)2^1}+\frac{1}{(\frac{3!}{2^1} \mod 2)2^1}++\frac{1}{(\frac{4!}{2^3} \mod 2)2^3}+\frac{1}{(\frac{5!}{2^3} \mod 2)2^3}+\frac{1}{(\frac{6!}{2^4} \mod 2)2^4}\ldots$

The motivation to find this sum is analyze some properties of the prime numbers using the expansion of $e$.

Matrices. $XX^t=A$. $X=?$

2011-11-06T22:35:54Z

$$XX^t=A,\quad (X_{ij}\in\text{{0,1}}, \quad \sum_{j=1}^m x_{ij}=2)$$

How to find all matrices $X$ which satisfy this equation?

These articles maybe could help us:

Completely Positive Matrices

Solving X times Transpose of X Is Equal to A - Over Integers (Which he claims to find all $X$ to satisfies, but in Integers, maybe we can transform this solution to this problem and find the solutions).

How to prove? Prime numbers.

2011-11-02T15:42:27Z

$f(0)=4$

$f(x+1)=f(x)^2-2$

$\text{if} \quad 2^{x+2}-1|f(x) \quad \text{then} \quad 2^{x+2}-1 \quad \text{is prime}$

How to prove that?

Example:

$x=1$

$f(1)=14$,

$2^{1+2}-1=7$

and

$7|f(1) \implies 7$ is prime.

How to isolate $f(x)$ in $f(x+a)=f(x)+a\times g(x)$?

2011-10-31T22:27:19Z

$a \in \mathbb{R}$

$f:\mathbb{R} \rightarrow \mathbb{R}$

$g:\mathbb{R} \rightarrow \mathbb{R}$

For generic functions $f$ and $g$, how isolate $f(x)$ in the equation below?

$f(x+a)=f(x)+a\times g(x)$

I tried to use Fourier Transform and Inverse Fourier Transform but looks like this don't work very well.

$f(x - a)=$ $e^{-2\pi i a \xi} \hat{f}(\xi)$

$\hat{f}(\xi)=$ $\int_{-\infty}^{\infty}f(x) e^{-2\pi i x\xi}\, dx \quad$ (Fourier Transform)

I tried ZTransform too, but again, didn't worked very well.

Odd perfect numbers. What's the best progess we now about them?

2011-10-31T13:43:20Z

Looks like no one found a odd perfect number.

Looks like too there's no proof saying no odd perfect numbers can exist.

Euler did a proof saying how all even perfect numbers should be, but what about the odd ones?

What we no about them?

Let $od$ a theorical odd perfect number, we know:

$op=p_1^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_n^{\alpha_n}$

$p_1,p_2,\cdots,p_n \in (P-2)$

$\alpha_1,\alpha_2,\cdots,\alpha_n \in N$

$op=2^{\alpha_1} p_2^{\alpha_2} p_3^{\alpha_3} \cdots p_n^{\alpha_n}+1$

$p_1,p_2,\cdots,p_n \in (P-2)$

$\alpha_2,\cdots,\alpha_n \in N$ and $\alpha_1 \in N^*$

In the first case is easy do a equation of summation of all divisor, but maybe there are something intersting in the second way too.

Comment by GarouDan

2011-11-30T10:23:10Z

If I need ask things here and just here (what's is annoying thing) tell me that I'll remember. But, but you may point in faq where is it? Or put there (not in meta) that's not a polite thing. Maybe I had been some agressive, but I think all community (even me, a beginner here) should opine to have a better site.

Comment by GarouDan

2011-11-30T10:19:08Z

Well it has been very difficult join to this community. I think I have good questions, with Mathematics interest (like said in faq). The truth is, I didn't asked here because I didn't get ansser in Math.SE, I asked here because I wanted too, I would like another different opinions. I had seen questions in Math.SE with over 30 votes with no answer and answered here. So, what's the problem? If I ask in Math.SE and write in the question, you close my question. I I ask there too and write in the question, you close my question. Do you hate the Math.SE, didn't like no cross platafform?

Comment by GarouDan

2011-11-28T16:41:08Z

@AH, What about if $f$ a polynomial or a analytic function.

Comment by GarouDan

2011-11-28T15:22:25Z

@JacquesCarette. I think you're right about the $S_f$ and $MS_f$. Your formula using $x_0=0$ and $m=2$ shows what I need. And you're right again when you say I'm looking for something like $MS_f(x,x_0,m)=\displaystyle\sum_{i=0}^{m-1}a_iS_f(w^ix)$. I already know this A=B book and it's really a good one, about the other I'm looking for. But isn't clear to me how to find this $a_i$'s, can you point something or a algorithm on the books to treat this?

Comment by GarouDan

2011-11-15T19:19:54Z

I think close isn't the better way to solve this. The question isn't "too localizable" (even in Math.SE) and have mathematician interest as in FAQ. About the motivation, the truth is I didn't have a theory yet and I'm asking some help (solving this question) to go ahead. Otherwise, where in FAQ says put questions in two different sites aren't allowed?

Comment by GarouDan

2011-11-07T01:40:38Z

@BrendanMcKay I will try to get this article and take a look and return... But I think this will not can help me so much, I need find the other solutions of this problem, because this solution, by adjacency matrix I already know but I need the others, if exists.

Comment by GarouDan

2011-11-07T01:37:49Z

@BrendanMcKay says, I'm investigating graphs but by linear algebra. And I think, but don't know why yet, it's possible find a good method to find the solutions because in that link of the integers matrices, he claims to find all integers matrices, so, binary matrices should be more easy to find but that process it's a bit fuzzy to me.

Comment by GarouDan

2011-11-02T00:04:27Z

Didn't understand very well. Can you give an example? For example, using $a=1$ ang $g(x)=\frac{-1}{x(x-1)}$ who mathematica don't solves.

Comment by GarouDan

2011-11-01T21:10:41Z

I think use DiracDelta is special functions no? And using Fourier Transforms, for example, DiracDelta appears frequently.

Comment by GarouDan

2011-11-01T14:09:24Z

@shrdlu Yes I agree, but if $f$ is unknown, how to find, at least, one solution to $f$?

Comment by GarouDan

2011-11-01T14:07:43Z

@BR , Are you saying it's possible find $f(x)$ in my exampling using Inverse Fourier Transform, but Mathematica, don't do it?

Comment by GarouDan

2011-11-01T14:05:47Z

@AliBleybel I can't embrace you answer as solution how it presents now. When I put the FourierTransform link and that formulas, I tried it before. I tried isolate $f(x)$ using that. And tried using [ZTransform](en.wikipedia.org/wiki/Z-transform) too. It's not a easy question. Maybe we can use ZTransform to several things and FourierTransform to many others and other transform and find all solutions. Don't know, but if $a=1$ or $a\implies 0$, I think there limitated solutions. And I'm searching a way to find them.

Comment by GarouDan

2011-10-31T23:23:16Z

If you have Mathematica you can try: a=1 G[x]=1/(x*(x-1)) F[y_]:=InverseFourierTransform[a*FourierTransform[G[x],x,k]/(E^(2*Pi*I*k*a)-1),k,y] and finally F[y] to see the results...but your kernel probably will works forever> So my new question is, Fourier and InverseFourier transforms can't solve this simple question?

Comment by GarouDan

2011-10-31T23:17:13Z

In Mathematica, if we try $a=1$ and $g(x)=\frac{-1}{x(x+1)}$ $f(x)=a (\mathcal{F}_{\xi }^{-1}[\frac{\mathcal{F}_x[G(x)](\xi )}{-1+e^{2 i \pi a \xi }}])(x)$ We have no answer, but, is easy to know the answer. $f(x)=\frac{1}{x}$ because, $f(x+1)=f(x)+1\times g(x) \iff \frac{1}{x+1}-\frac{1}{x}=g(x) \iff \frac{-1}{x(x+1)}=g(x)$

Comment by GarouDan

2011-10-31T23:02:37Z

@Qfwfq, isolate is find f or $f(x)=\cdots$, where $\cdots$ is something using $g$ and $a$.