User lwins.gafield - MathOverflow

For sum of unit-roots

2012-12-24T14:52:51Z

Define $\delta (0)=1$ and $\delta (x) = 0$ when $x \neq 0$.

Can we find a "good" method or algorithm to work out $$ S(n) = \sum_{k_1=0}^{n-1} \sum_{k_2=0}^{n-1} \cdots \sum_{k_n=0}^{n-1} \delta (\mathrm{e}^{2 \pi k_1 \mathrm{i} /n} + \mathrm{e}^{2 \pi k_2 \mathrm{i} /n} + \cdots + \mathrm{e}^{2 \pi k_n \mathrm{i} /n})$$

with any positive integer $n$?

(It's easy to count this when $n=p^l$ or $n=pq$. In particular, $S(p)=p!$ is obvious.)

Fourier Transform, for entire function

2012-12-02T09:05:42Z

On THIS site, Alexandre used Fourier transform to solve the problem.

If we use Fourier transform, how to define it to ensure any entire function has a FT?

Classical FT is defined by $$ \mathcal{F}[f] = F(\xi) = \frac{1}{\sqrt{2 \pi}}\int_{-\infty}^{+\infty}f(z)\mathrm{e}^{-\mathrm{i} \xi z} \mathrm{d} z. $$ This only work for $f \in L^1(\mathbb{R})$. (If improved, it can work for $f \in L^2(\mathbb{R})$.)

I know $\mathcal{F}[\mathrm{e}^{sz}] = \sqrt{2 \pi} \delta(\xi - \mathrm{i}s)$, but I'm not sure about a general definition.

On equation f(z+1)-f(z)=f'(z)

2012-11-29T12:03:38Z

Original Problem

If $f$ is an entire function such that $$ f(z+1)-f(z)=f'(z) $$ for all $z$. Is there a non-trivial solution? ($f(z)=az+b$ is trivial)

And here is something uncertainty

If we use Fourier transform, how to define it to ensure any entire function has a FT?

I know $\mathcal{F}[\mathrm{e}^{sz}] = \sqrt{2 \pi} \delta(\xi - \mathrm{i}s)$, but I'm not sure about a general definition.

Answer by Lwins.Gafield for A special case of Catalan's conjecture

2012-11-07T13:40:27Z

I think this gives a nice elementary solution, too. See this: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=505773

A special case of Catalan's conjecture

2012-11-06T04:55:16Z

Solve equation $$ y^p - (2^p-1)^x = 1 $$ where $x,y>0 \in \mathbb{Z}$, $p \in \mathbb{P}$. Is there a elementary method to do it? Thanks. =)

Is $2$ always a $p^{\rm th}$-power nonresidue modulo $2^p-1$?

2012-11-04T03:07:21Z

That is, is following inequality holds while $p \in \mathbb{P}$? $$ x^p \neq 2 \ (\mathrm{mod} \ 2^p-1) $$ Certainly $x \in \mathbb{Z}$.

Equation system on Z[x]

2012-11-02T07:07:05Z

Can we solve this equation system when $n=2,3,4,\cdots \ $ is given? $$ F(x)+F((2^n-1)x) = (G(x))^nx^g $$ $$ 2F(2^{n-1}x) = (H(x))^nx^h $$ While $F,G,H \in \mathbb{Z}[x]. g,h \in \mathbb{N}.$

Another Number Theory Question about Polynomial

2012-10-28T16:38:06Z

We know following theorem by Schur: Suppose that $f(x) \in \mathbb{Z}[x]$ is a polynomial such that exists an integer $m$ such that $f(n) = m^2$ for every integer $n$. Then $f(x) = g(x)^2$ for some $g(x) \in \mathbb{Z}[x]$.

Is this true if I using $3,4,5 \cdots$ instead of $2$?

A Number Theory Question about Polynomial

2012-10-28T13:55:41Z

Now we have a Polynomial $P(n)$ on $\mathbb{Z}[x]$. It can't be wriiten as $P(n)=F(n)G(n)$ while $F(n),G(n) \neq 1$. Is it right that for any $P(n)$, there is a $n$ such that $P(n)$ is a prime? Is it right that for any $P(n)$, there is a $n$ such that $P(n)$ is not a square-number?

A problem in number theorem with a number of the base p

2012-05-18T06:53:45Z

First we define a function $f(x,p)$, with $x$ a natural number and with $p$ a prime number.

$f(x,p)$ stands for the location where the digit "$p-1$" first appears in the base-$p$ expansion of $x$. If the digit "$p-1$" doesn't appear, $f(x,p)$ will be equal to $-\infty$. That is, if $x=\sum_{i\geq 0} a_i p^i$ with $0\leq a_i < p$, then $f(x,p)=\min\{i : a_i=p-1\}$. For example:

$f((122)_3,3)=0$;
$f((561603)_7,7)=2$;
$f((123)_5,5)=-\infty$;
$f((651634316331)_7,7)=3$.

Now consider a positive integer $A=(a_m a_{m-1} \cdots a_1a_0)_p$ with $f(A,p)=m$, i.e., $a_m=p-1$, $a_0,a_1,\cdots,a_{m-1}\neq p-1$.

My problem is how to prove that for any $h \in [0,2^{m-1}-1]\cap \mathbb{Z}$, which has at most $p-1$ digit "$1$" in binary representation. there is a $k \in \mathbb{Z}^+$ with $A-(p-1)k \geq 0$, satisfies that,

$$2^{f(A-k,p)} \ \mathbf{xor}\ 2^{f(A-2k,p)} \ \mathbf{xor} \ \cdots \ \mathbf{xor} \ 2^{f(A-(p-1)k,p)} = h$$

Edit: I (the one making the edit, not the OP) am not sure how to parse the problem. Is the following equivalent?

Let $h_0,h_1,\dots, h_{m-2}\in \{0,1\}$ with $\sum h_i < p$. Is there necessarily a positive integer $k$ with $A-(p-1)k\geq0$ and for $0\leq i \leq m-2$ $$\left| \{ j : 1\leq j < p, f(A-jk,p)=i \} \right| \equiv h_i \pmod{2}?$$

To Kevin O'Bryant,

Yes, it's equivalent to my version.

An asymptotic series for the digamma function

2012-05-07T12:04:18Z

As we know, there is an asymptotic series for the digamma function when $z>0$ is a real number. $$ \psi(z)=\ln z+\sum_{n=1}^{\infty}{\frac{B_n}{nz^n}} $$ $B_n$ is the first Bernoulli numbers.

How to make a proof?

Answer by Lwins.Gafield for An asymptotic series for the digamma function

2012-05-07T14:19:45Z

We can prove this, using Euler-Maclaurin Formula. Here is a introduction from Wikipedia. http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula

This is a quite easy problem. To Admin, You may be able to consider deleting this question, thanks. ^_^

A random walk with uniformly distributed steps

2012-04-16T16:14:44Z

The following problem has bothered me for a long time.

Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly in the following way. For every step of the "walk", it will choose a real number $\Delta x$ uniformly from the interval $[-1,1]$, turn right, and move $\Delta x$ unit. Once it reaches the left side of the point $O$, it will "die" immediately.

Our task is find out the probability of the point is alive after $n$ steps of "walk" $P_n$. I guess that $P_n=\frac{(2n)!}{4^n (n!)^2}$, but I can't prove this or explain why it is true.

Generating Permutations with Given Set

2012-04-27T08:07:19Z

Let $S_n$ be the set of all permutations that act on $1...n$. You are given a subset $P\subseteq S_n$, and you are to compute the size of the set $G(P) \subseteq S_n$, where $G(P)$ meets the following requirements:

$G(P)$ contains the identity permutation,
$P \subseteq G(P)$,
$G(P)$ is closed under taking inverses and multiplications (if $a, b \in G(P)$, then $ab \in G(P)$, if $a \in G(P)$, then $a^{-1} \in G(P)$),
$G(P)$ is a minimal possible set that meets requirements 1,2 and 3.

Is there a method or algorithm that can solve this?

A random walk with uniformly distributed steps II

2012-04-20T07:12:39Z

The problem is a improved version of this problem, http://mathoverflow.net/questions/94226/

Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly. For every step of the "walk", it will choose a real number $\Delta x$ in interval $[l,r]$ equiprobably, and turn right and move $\Delta x$ unit. Once it move to the left side of the point $O$, it will "die" immediately.

Our task is find out the probability of the point "live" after n steps of "walk" $P_n$. I have tried to solve it and found out a method to count $P_n$ with $\Theta (n^5)$ of time complexity, using fourier transform and something in complex analysis. But is there a more simple method? Or is there one which needs lower time complexity?

Comment by Lwins.Gafield

2012-12-11T07:03:16Z

Yet I'm doing this in $\mathbb{C}$, by that, FT and LT are equivalent. Thus, if we can define LT as your state, then, we can do FT as well.

Comment by Lwins.Gafield

2012-12-02T11:33:08Z

Mmm.. Then, is a entire function $f$ have a Fourier transform $F$ (perhaps $F$ is a distribution) for sure? If not, then the answer for [THIS][1] is incomplete. [1]: mathoverflow.net/questions/114875

Comment by Lwins.Gafield

2012-12-02T07:11:47Z

Excellent, but how to define "Fourier Transform" to ensure that any possible entire function have its FT? Classical FT is only defined in $L^2(\mathbb{R})$.

Comment by Lwins.Gafield

2012-11-06T07:38:51Z

To Johan, obviously $(y-1,\frac{y^p-1}{y-1})=(y-1,p) \mid p$. So show that $p \nmid y-1$ is enough. It's trivial because $y \equiv 1 \pmod p \implies (2^p-1) \equiv 0 \pmod p$.

Comment by Lwins.Gafield

2012-11-06T07:31:33Z

I'm grateful for your patient. Very nice answer, I think. Thanks. =)

Comment by Lwins.Gafield

2012-11-06T06:38:11Z

Dear Johan, sorry, I've modified it. Now $(1,2)$ is a solution.

Comment by Lwins.Gafield

2012-11-06T05:54:39Z

Dear Will, but it's toooo hard to show that Catalan's conjecture is right. Can we find a easier proof? Dear Johan, there are only a solution $(x,y)=(1,2)$.

Comment by Lwins.Gafield

2012-11-02T10:06:01Z

And, $a,b>0$. $n$ is given. "we have" means "we can find".

Comment by Lwins.Gafield

2012-11-02T10:03:01Z

Mmm.. It's about this problem: for any $a+b=k^n$, we have a $l$ such that $F(a)+F(b)=l^n$, solve for $F$. Certainly $F \in \mathbb{Z}[x]$.

Comment by Lwins.Gafield

2012-11-02T09:13:00Z

I wanted to solve for all $(F,G,H,g,h)$.

Comment by Lwins.Gafield

2012-10-28T16:25:51Z

Dear François Brunault, thank you, that helps me a lot. \\ Dear Goldstern, +-1. \\ Dear Noam D. Elkies, I've been showed something interesting by you, thanks.

Comment by Lwins.Gafield

2012-10-28T14:22:28Z

Thanks. I've modified it.

Comment by Lwins.Gafield

2012-05-21T04:40:03Z

To Karl Schwede, $\mathbf{xor}$ is always acting of base 2.

Comment by Lwins.Gafield

2012-05-20T22:53:23Z

Thanks. I've fixed some error in the problem.

Comment by Lwins.Gafield

2012-05-18T12:47:35Z

To David Roberts, This problem is closely related to how to find the identity of this function, $$F(x)=\mathbf{mex}(\{F(x-k) \ \mathbf{xor}\ F(x-2k)\ \mathbf{xor} \cdots \mathbf{xor} \ F(x-(p-1)k) \ | \ k \in \mathbb{Z}^+ , x-(p-1)k\geq 0\})$$