User greg martin - MathOverflow

Answer by Greg Martin for Are sums of the inverses of prime siblings finite?

2013-05-21T05:46:57Z

It turns out that $S_d$ is finite for every $d$. See my answer to this very similar question.

Answer by Greg Martin for Another colored balls puzzle

2013-05-13T18:49:22Z

I've calculated rigorously that the expectations for $n=1,2,3,4$ are $0,1,3,6$ respectively. For example, when $n=4$:

One turn brings the balls to a 211 state (meaning 2 balls of one color and 1 ball each of two more colors).
From a 211 state, there is a $2/5$ probability of going to another 211 state, a $2/5$ probability of going to a 31 state, and a $1/5$ probability of going to a 22 state.
In other words, there is a $2/5$ probability of staying in the 211 state and a $3/5$ probability of leaving it; the expected number of turns it takes to leave the 211 state is thus $1/(1-2/5) = 5/3$. When it does leave, there's a $2/3$ probability of being in a 31 state and a $1/3$ probability of being in a 22 state.
By Gambler's Ruin, the expected number of turns to go from the 22 state to the 4 state is $2(4-2)=4$, while the expected number of turns to go from the 31 state to the 4 state is $3(4-3)=3$.
Therefore, the total expected number of turns for the $n=4$ game is $1 + 5/3 + (\frac23\cdot 3 + \frac13\cdot 4) = 6$.

Moreover, I've run simulations for $n=5,6,7$. The data strongly suggests that the expectations are $10,15,21$ respectively.

I am thus persuaded to conjecture that the expected stopping time for $n$ balls in general is exactly $\binom n2 = n(n-1)/2$.

Answer by Greg Martin for average involving phi function

2013-05-07T02:44:55Z

The expression converges to $0$, even when $\phi(n)$ is replaced by the larger $n$. The contribution from $n\le\sqrt N/d$ can be given by ignoring the logarithm in the denominator: \begin{align*} \frac1{N^2} \sum_{d=1}^N \log d \sum_{n=1}^{\sqrt N/d} \frac{\phi(n)}{\log dn} &\le \frac1{N^2} \sum_{d=1}^N \log d \sum_{n=1}^{\sqrt N/d} n \\ &\lesssim \frac1{N^2} \sum_{d=1}^N \log d \cdot \frac12 \bigg( \frac{\sqrt N}d \bigg)^2 \\ &= \frac1{2N} \sum_{n=1}^\infty \frac{\log d}{d^2} = \frac{|\zeta'(2)|}{2N}. \end{align*} (The exact value of the sum over $d$ isn't important - the fact that it converges is enough to show that the limit equals $0$ as $N\to\infty$.) The remaining contribution can be given by simplifying the logarithm in the denominator: \begin{align*} \frac1{N^2} \sum_{d=1}^N \log d \sum_{n=\sqrt N/d}^{N/d} \frac{\phi(n)}{\log dn} &\le \frac1{N^2} \sum_{d=1}^N \log d \sum_{n=1}^{N/d} \frac n{\log \sqrt N} \\ &\lesssim \frac2{N^2\log N} \sum_{d=1}^N \log d \cdot \frac12 \bigg( \frac Nd \bigg)^2 \\ &= \frac1{\log N} \sum_{n=1}^\infty \frac{\log d}{d^2} = \frac{|\zeta'(2)|}{\log N}, \end{align*} which also tends to $0$ as $N\to\infty$.

Answer by Greg Martin for Least non primitive root

2013-04-29T01:15:34Z

Trivially, any upper bound for the least prime quadratic residue modulo $p$ is also an upper bound for the least prime non-primitive root modulo $q$. I can't recall what's been proved about the latter problem assuming GRH (probably a power of $\log q$), but that will form a good conjectural upper bound.

As for a conjectural lower bound, given an odd integer $n$, there are presumably infinitely many primes $q$ in any fixed residue class $a\pmod{8n}$ such that $(q-1)/2$ is also prime, as long as $a-1$ is not divisible by any prime dividing $n$. Taking $n$ to be the product of all the odd primes up to $z$, so that $n \approx e^z$, we expect to find such a prime $q$ no larger than $e^{(1+o(1))z}$. If we choose $a$ appropriately, then all primes up to $z$ will be quadratic residues modulo $q$; since $(q-1)/2$ is also prime, all quadratic residues are primitive roots. This argument gives a conjectural lower bound of about $\log q$ for the smallest prime non-primitive root.

Answer by Greg Martin for Uniform convergence of $g(x) = \sum_{n=1}^\infty (1-x) a_n x^n$

2013-04-28T16:27:49Z

I suspect that putting in a double pole at $x=1$ will show this implication to be false. In other words, take $f(x) = x/(1-x)^2 = \sum_{n=1}^\infty nx^n$. Then $g(x) = (1-x)f(x)$ still satisfies $\lim_{x\to1^-} g(x) = \infty$, which should rule out uniform convergence. (Don't know why you're starting your power series at $n=1$, by the way.)

Answer by Greg Martin for Is rigour just a ritual that most mathematicians wish to get rid of if they could?

2013-04-17T21:59:20Z

An analogous question in physics might be: Is relativity just a ritual that most physicists wish to get rid of if they could? When we're going about our daily lives, most of the time people don't care about relativity: Newtonian physics explains everything we're going to see, it's simpler, and it's intuitive. We wouldn't bother to set up a relativistic calculation to decide when the bus is going to arrive. But in situations where our intuition is lacking, and/or it's really important to us that our answer is correct, then we need to incorporate relativity (and sometimes we learn that our intuition isn't always dependable!).

In math, when we're going about our daily lives, most of the time people don't care about rigor: intuitive arguments, exhibiting a few terms in a pattern, and arguing from experience and approximation work pretty well. We wouldn't bother setting up an integral to calculate how far our car gets on a tank of gas. But in situations where our intuition is lacking, and/or it's really important to us that our answer is correct, then we need to incorporate rigor (and sometimes we learn that our intuition isn't always dependable!).

Answer by Greg Martin for Transcendency of numbers of a special form.

2013-04-11T07:45:17Z

If you allow $S$ to be finite, then the answer is no: any real number $x\in(0,\frac{\pi^2}6-1)$ can be written as $\sum_{r\in R} r^{-2}$ for some set $R$ of positive integers with positive density.

To see this, first choose $m\ge2$ such that $m^2x > \frac{\pi^2}6$, and let $R_1 = m\mathbb N$, so that $\sum_{r\in R_1} r^{-2} = \frac{\pi^2}{6m^2} < x$. Then use the greedy algorithm: recursively define $n_k$ to be the least positive integer not in $R_1 \cup \lbrace n_1,\dots,n_{k-1}\rbrace$ such that $\sum_{j=1}^k n_j^{-2} < x - \frac{\pi^2}{6m^2}$. Setting $R_2 = \lbrace n_1,n_2,\dots \rbrace$ and $R=R_1\cup R_2$, we see that $\sum_{r\in R} r^{-2} = x$. One can show that $R_2$ has density 0: if $x_k = x - \frac{\pi^2}{6m^2} - \sum_{j=1}^k n_j^{-2}$, then the fact that $n_k^{-2} < x_{k-1} \le (n_k-1)^{-2}$ show that $x_k \le (n_k-1)^{-2} - n_k^{-2} < 2n_k^{-3} < 2x_{k-1}^{3/2}$, and so the $n_k$ form a very sparse set.

I believe a similar proof will show the following: given any subset $S$ of $\lbrace2,3,4,\dots\rbrace$, there exists $x_0(S)>0$ such that any real number $x\in(0,x_0(S))$ can be written as $\sum_{r\in R} \sum_{s\in S} r^{-s}$ for some set $R$ of positive density. (Basically, one replaces the function $t^{-2}$ in the previous proof with the function $\sum_{s\in S} t^{-s}$.)

Answer by Greg Martin for Ordinary Generating Function for Mobius

2013-04-03T20:46:28Z

For (2), the answer is yes - see for example this paper of Baker and Harman.

Answer by Greg Martin for Two different definitions of Erdos-Rényi random graph

2013-04-02T21:41:01Z

If I understand the first fact correctly, I find it hard to believe how it could be true. As you say, $G_n$ is unlikely to have exactly $[cn]$ edges, while the right-hand side always does.

As for the second fact: Think of choosing the edges for $G_n^*$ one at a time, and what could happen to make the graph not simple. For the first edge, there is an $n/n^2$ probability that we get a loop; so there's a $1-1/n$ probability of being simple after the first edge. For the second edge, we have the same $n/n^2$ chance of getting a loop, and an additional $2/n^2$ chance of repeating the first edge ($2$ because we could swap the endpoints); so there's a $(1-1/n)(1-1/n-2/n^2)$ probability of the graph being simple after the second edge. Continuing in this way, we see that the probability of the graph being simple after all $m$ edges are placed is $$ \prod_{j=0}^{m-1} \bigg( 1 - \frac1n - \frac j{n^2} \bigg). $$ This can be bounded below:

$$ \prod_{j=0}^{m-1} \bigg( 1 - \frac1n - \frac j{n^2} \bigg) \ge \bigg( 1 - \frac{n+m-1}{n^2} \bigg)^m \ge \bigg( 1-\frac{c+1}n \bigg)^{cn}. $$ This last quantity tends to $e^{-c(c+1)}$ as $n$ goes to infinity; in particular, it is bounded below uniformly for $n$ sufficiently large in terms of $c$. (That's the best we can hope for: if $c=100$, then there's no chance that the $G_n^*$ graph is simple if $n\le200$ - there aren't enough distinct edges.)

Answer by Greg Martin for A question on the number of subgroups of a given exponent of a finite abelian p-group

2011-10-24T06:59:21Z

I had to look this up as well at some point in my research. The answer is yes, and a Google search for "number of subgroups of an abelian group" leads to several downloadable papers, not all of them easy to read. The paper "On computing the number of subgroups of a finite abelian group" by T. Stehling, in Combinatorica 12 (1992), contains the following formula and (I think) references to where it has appeared earlier in the literature.

Let $\alpha = (\alpha_1,\dots,\alpha_\ell)$ be a partition, so that $\alpha_1\ge\cdots\ge\alpha_\ell$. (In this formula it is convenient to allow some of the parts of the partition at the end to equal 0.) Define the notation $$ {\mathbb Z}_\alpha = {\mathbb Z}/p^{\alpha_1}{\mathbb Z} \times \cdots \times {\mathbb Z}/p^{\alpha_\ell}{\mathbb Z} $$ for a general $p$-group of type $\alpha$. Define similarly a partition $\beta$, and suppose that $\beta\preceq\alpha$, meaning that $\beta_j\le\alpha_j$ for each $j$. We want to count the number of subgroups of ${\mathbb Z}_\alpha$ that are isomorphic to ${\mathbb Z}_\beta$ .

Let $a=(a_1,\dots,a_{\alpha_1})$ be the conjugate partition to $\alpha$, so that $a_1=\ell$ for example; similarly, let $b$ be the conjugate partition to $\beta$. Then the number of subgroups of ${\mathbb Z}_\alpha$ that are isomorphic to ${\mathbb Z}_\beta$ is $$ \prod_{i=1}^{\alpha_1} \genfrac{[}{]}{0pt}{}{a_i-b_{i+1}}{b_i-b_{i+1}}p^{(a_i-b_i)b_{i+1}}, $$ where $$ \genfrac{[}{]}{0pt}{}nm = \prod_{j=1}^m \frac{p^{n-m+j}-1}{p^j-1} $$ is the Gaussian binomial coefficient.

To answer your specific question, you'd want to sum over subpartitions $\beta\preceq\alpha$ such that $\beta_1$ equals the exponent in question.

Answer by Greg Martin for product 1+1/p in terms of Chebyshev's theta or psi function

2013-03-30T04:09:33Z

If you really wanted to, you could use partial summation to write $$ \log \prod_{x < p\le y} \bigg( 1+\frac1p \bigg) = \theta(y)f(y) - \theta(x)f(x) - \int_x^y \theta(t)f'(t)\ dt, $$ where $f(t) = \log(1+1/t)/\log t$. But I suspect the most useful thing one can say about your product follows from what quid said: $$ \prod_{x < p\le y} \bigg( 1+\frac1p \bigg) = \frac{\log y}{\log x} \bigg( 1 + O\bigg( \frac1{\log x} \bigg) \bigg) $$

Answer by Greg Martin for Which real scalings of the natural numbers approximately accommodate the unbounded powers of a noninteger?

2013-03-25T03:09:04Z

This is a hard problem in general. For example, one might expect that the powers of $e$ have more or less randomly distributed fractional parts. However, I believe we can't even disprove that the fractional parts of powers of $e$ approach $0$. In other words, we can't disprove that $1$ is in your set $\Lambda$ (with $\alpha=e$). (For all I know, we can't disprove that any $\lambda$ is in your set, even with $\alpha=e$.)

Answer by Greg Martin for probability density function

2013-03-24T20:18:41Z

First, you should probably solve the problem first without the two cases and the $+\pi$; the symmetry of switching $(X_1,Y_1)$ with $(X_2,Y_2)$ will allow you to convert your answer to the simpler problem - some pdf $f(x)$ supported on $(-\frac\pi2,\frac\pi2)$ - to the answer you're really looking for - which will be $\frac12f(x) + \frac12f(x-\pi)$.

Second, I recommend trying to find the probability density function $g(x)$ for $\frac YX$, given that $X$ and $Y$ are independent random variables both with the triangle distribution on $(-1,1)$ - this is a ratio distribution. Afterwards you can adjust your answer to accommodate the $\tan^{-1}$ function: the resulting probability density function will be $g(\tan^{-1} x)/(1+x^2)$.

Answer by Greg Martin for Order of difference of two generators of cyclic group

2013-03-11T03:51:58Z

The way I would solve this problem (spoiler alert: I'm only going to start a solution, not carry it all the way through) is as follows. Let $m$ be the order of the cyclic group (here $m=2^n-1$, but the more general problem is no harder), and let $k$ be any divisor of $m$. Let $f(k)$ denote the number of ordered pairs of generators $(\alpha,\beta)$ of the cyclic group such that $k(\alpha-\beta)=0\pmod m$. Let $h(k)$ denote the number of such ordered pairs such that $\alpha-\beta$ has order exactly $k$. It's clear that $f(k) = \sum_{b\mid k} h(b)$, and so Möbius inversion gives $h(k) = \sum_{a\mid k} f(b) \mu(k/a)$. Therefore it suffices to find a formula for $f(k)$.

Let $g(\alpha)$ be the indicator function of generators of the cyclic group. Since $\alpha$ is a generator exactly when $\gcd(\alpha,m)=1$, we see that $$ g(\alpha) = \sum_{d\mid \gcd(\alpha,m)} \mu(d). $$ Therefore \begin{align*} f(k) &= \sum_{1\le\alpha\le m} g(\alpha) \sum_{1\le b\le m/k} g(\alpha+kb) \\ &= \sum_{1\le\alpha\le m} \sum_{c\mid \gcd(\alpha,m)} \mu(c) \sum_{1\le b\le m/k} \sum_{d\mid \gcd(\alpha+kb,m)} \mu(d) \\ &= \sum_{c\mid m} \mu(c) \sum_{d\mid m} \mu(d) \sum_{\substack{1\le\alpha\le m \\ c\mid \alpha}} \sum_{\substack{1\le j\le m/k \\ d\mid(\alpha+jk)}} 1. \end{align*} The inner double sum is a counting problem, and it will depend upon the common factors of $c$, $d$, and $k$, but it should be doable. And then the formula for $f(k)$ should reduce to some multiplicative-function-type sum (hence so will that for $h(k)$).

Answer by Greg Martin for How long should one wait for a report before asking about its status?

2013-03-10T21:38:26Z

As others have mentioned, possible parameters are too wide for a one-size-fits-all answer. But here are some data points:

My personal default is to wait six months before inquiring into a paper's status. In other words, I have decided that not hearing anything in six months is pretty much never a surprising turn of events to me.
For a long paper (say over 40 pages), I might extend this somewhat, but probably not longer than nine months. For a very short paper (say under 8 pages), I might inquire at four months; but knowing me, I'd probably just wait until six months anyway.
Surely these durations can be decreased if one is in the position where a paper accepted or not will have a significant impact upon one's career. I think it's reasonable to write after three months, politely ask about the status of the paper, and add that you're going on the job market at time X and would be very grateful to know the decision on the paper by then.
Above all else, word your inquiry with the understanding that both the editors and referees are volunteering their time. Authors have the right to a timely evaluation of their paper (that comes with the agreement not to submit elsewhere while it's being evaluated), and sometimes the editors/referees just need a gentle nudge to notice that it's been a long time. But (needless to say) implying malice, laziness, or incompetence is extremely unlikely to make anything better. (Even if it's the third time around asking about a paper, when those nouns probably do in fact apply!)

Answer by Greg Martin for Estimating $\prod_{p\mid n}(1+1/p)$ in terms of n

2013-03-08T20:41:27Z

If you want a weaker bound that is completely explicit, the following method is pretty simple. Let $\omega(n)$ denote the number of distinct prime factors of $n$. Since the function $1+1/x$ is a decreasing function of $x$, and the smallest prime equals 2, we certainly have $$ \prod_{p\mid n} \bigg( 1+\frac1p \bigg) \le \prod_{k=2}^{\omega(n)+1} \bigg( 1+\frac1k \bigg) = \frac{\omega(n)+2}2 $$ since the product telescopes. Moreover, $\omega(n) \le (\log n)/(\log 2)$, again since each prime factor of $n$ is at least 2. Therefore $$ \prod_{p\mid n} \bigg( 1+\frac1p \bigg) \le \frac{\log n}{2\log2}+1 $$ (with equality at $n=1$ and $n=2$).

Answer by Greg Martin for Natural density of a set of positive integers not in certain congruence classes

2013-02-28T17:17:54Z

Such a generalization would probably be false. Choose any infinite set $M$ of positive integers, however sparse you want, so that $\sum_{m\in M} 1/m$ definitely converges. Now choose the first $N_m$ to be ${1}$, the second $N_m$ to be ${2}$, and so on. Then every single positive integer is congruent to one of the targeted residue classes.

For example, take $m_k = 3^{4^k}$ and set $M = { m_1,m_2,\dots }$ and $N_{m_k} = {k}$; then every $k\equiv k\pmod{m_k}$, and so the set of "surviving" positive integers is empty.

I just realized that this doesn't exactly answer your question, since the empty set does have a natural density! But this construction does show, I think, that the spirit of your conjecture isn't right - you won't just get a happy sieved set in general, depending on the specific choice of the $N_m$.

Answer by Greg Martin for Generators of symmetric group

2013-02-21T21:19:11Z

I believe that the two permutations $$ (1\ 2\ 3)(4\ 7\ 5\ 8\ 6\ 9) \quad\text{and}\quad (4\ 5\ 6)(1\ 7\ 2\ 8\ 3\ 9) $$ generate a subgroup of $S_9$ of order only $162$.

Answer by Greg Martin for Alternating series test for non-decreasing terms

2013-02-21T01:11:49Z

$$f(x) = \frac{2(\cos \pi x/2)^2}{x} + \frac{(\sin \pi x/2)^2}{2^{(x-1)/2}}$$ is certainly a function in the class you describe, but $f(2n) = 1/n$ and $f(2n+1)=1/2^n$, which breaks the alternating series test as you've remarked.

Answer by Greg Martin for Counting complex solutions on a disk.

2013-02-18T22:14:01Z

For $r=1$, the function $f(z) = (z+\sqrt2)^4$ works nicely. The path integral equals $0$, while the count on the right-hand side is always at least 1. (In fact, if you reduce $\sqrt2$ slightly, you can get the count to be at least 2 always.)

To deduce how I came up with this function, consider it as the composition of $z\mapsto z+\sqrt2$ with $z\mapsto z^4$, and think about what each map does to the complex plane.

Answer by Greg Martin for Equivalence of two well-known forms of (RH): reference-request.

2013-02-18T04:00:42Z

The argument that (2) implies (1) is given as equation (13.5) in Montgomery and Vaughan's Multiplicative Number Theory I. Classical Theory. A similar partial summation argument (probably two lines long instead of one) will establish that (1) implies (2).

Answer by Greg Martin for On a sum involving prime numbers

2013-02-11T19:54:43Z

Nature wants to count the primes up to some cutoff point $x$; when we humans insist on labeling the $n$th prime as the $n$th prime, we are destined to have very large error terms. Here, I don't know that you're going to do much better than just substituting in an asymptotic expression for the $k$th prime, changing the problem immediately to something like $$ \sum_{k=1}^n [k^a-(k-1)^a] \bigg( k\log k + k\log\log k - k + \frac{k\log\log k - 2k}{\log k} + O\bigg( \frac{k(\log\log k)^2}{\log^2k} \bigg) \bigg), $$ and then estimating each piece of this sum using regular analysis, divorced from number theory.

Answer by Greg Martin for Sums of two squares: What is known about the distribution of r(n)?

2013-02-10T07:17:28Z

I don't believe your new conjecture is true. Taking $b=a+\sqrt a$ for concreteness: standard sieve results show that the number of integers in $[a,b]$ that can be represented as the sum of two squares is $O(\sqrt{a/\log a})$. (This is closely related to the fact that the counting function of the sums of two squares is asymptotic to a constant times $x/\sqrt{\log x}$.)

Answer by Greg Martin for On a result of Montgomery and Vaughan about Euler's totient

2013-02-07T00:02:36Z

It's not a typo - I've read the proof before (the proof, by the way, doesn't invoke complex analysis at any point; it's very hands-on).

We're used to using Perron's formula / Mellin transforms to write the summatory function of an arithmetic function (such as $\Lambda(n)$ or $\phi(n)$) as a integral over a vertical contour, then moving that contour to the left and saying that the asymptotic behavior of the summatory function is governed by the residues of the poles we move the contour over. But that can only be rigorously established when the remaining part of the contour can be suitably estimated. I think if you try to apply this method here, you'll find that the integrand simply cannot be estimated nicely enough to make the argument work.

Answer by Greg Martin for Probability of all combinations of k numbers among n being coprime

2013-01-20T20:13:48Z

For any prime $q$, define $$ \ell(q,n,k) = q^{-n} \sum_{j=0}^{n-k} \binom nj (q-1)^j, $$ so that $\ell(q,n,k)$ is the probability, if a biased coin that comes up heads only $1/q$ of the time is tossed $n$ times, that at least $k$ heads are obtained. Equivalently, $\ell(q,n,k)$ is the probability, if $n$ numbers are chosen uniformly and independently from the set ${0,1,\dots,q-1}$, that at least $k$ of the numbers equal $0$.

Then the same argument giving the $1/\zeta(n)$ result shows that the probability that the greatest common divisor of every $k$-subset of $n$ "randomly chosen" integers is $1$ equals $$ \prod_q \big( 1 - \ell(q,n,k) \big), $$ where the product is over all primes $q$. This product is convergent as long as $k\ge2$; it diverges to $0$ if $k=1$ (appropriately).

For example, if three integers are chosen at random, the probability that they are pairwise coprime is $$ \prod_q \big( 1 - \ell(q,3,2) \big) = \prod_q \bigg( 1-\frac1q \bigg)^2 \bigg( 1+\frac2q \bigg) \approx 0.286747. $$ (A million trials with random integers between $1$ and $10^{60}$ yielded $286912$ pairwise coprime triples, so this limiting probability seems accurate.) I don't believe this product has a closed form in terms of the zeta function.

Answer by Greg Martin for How to prove $A^x\equiv A^{(x\: mod\: \varphi (c)+\varphi (c))}(mod\: c)(x\geq \varphi (c))$?

2013-01-18T20:32:20Z

Decompose $A=BC$ where $\gcd(B,c)=1$ and all the primes that divide $C$ also divide $c$. Then you can prove that $B^x \equiv B^{(x\mod \phi(c))} \equiv B^{\phi(c) + (x\mod \phi(c))} \pmod c$ by Euler's extension of Fermat's little theorem.

As for $C$, as long as $k$ exceeds the exponent of any prime dividing $c$ (in particular, as long as $k$ exceeds $\phi(c)$), you can show that $C^k \equiv C^{k+\phi(c)}\pmod c$. (This can be shown by looking at $C\pmod{c_1}$ and $C\pmod{c_2}$ separately, where $c=c_1c_2$, $\gcd(c_1,C)=1$, and the primes dividing $c_2$ and $C$ are identical.)

Answer by Greg Martin for Is every Fibonacci number "Fibonacci-prime"?

2012-11-29T09:47:59Z

As François Brunault said in his comment, your #2 is true: Carmichael's theorem, which establishes the existence of a primitive prime divisor of $F_n$ for every $n\ne1,2,6,12$, together with $\gcd(F_m,F_n) = F_{\gcd(m,n)}$, shows that no Fibonacci numbers are divisible by a primitive prime divisor of $F_n$ except $F_{kn}$.

This gives an answer to #1 as well: suppose that $F_n \mid F_a F_b$, and let $p$ be a primitive prime divisor of $F_n$. Then $p \mid F_a$ or $p\mid F_b$, and so one of $a$ or $b$ must be a multiple of $n$, so that $F_n\mid F_a$ or $F_n\mid F_b$. This proof doesn't work for $n=1,2,6,12$, but $n=1,2$ are trivial, and the cases $n=6,12$ follow by considering the (periodic) Fibonacci sequence modulo $8$ and $144$, respectively. (In the latter case it may be easier to examine the periodic sequence $\gcd(F_n,144) = F_{\gcd(n,12)}$.)

Note that this proof gives the generalization that if $F_n$ divides the product of any finite number of Fibonacci numbers, then it must divide one of them - except for $n=6$ and $n=12$ for which this is false!

Answer by Greg Martin for $\zeta(2k+1)$ expressed in a product of two infinite products of non-trivial zeros.

2012-11-21T08:45:57Z

(1) Yes: multiplying your Hadamard products for $\zeta(2k+1)$ and $\zeta(2k)$ and then dividing by the known formula $\zeta(2k) = |B_{2k}|(2\pi)^{2k}/2(2k)!$, we obtain $$ \zeta(2k+1) = \frac1{(2k-1)2k(2k+1)|B_{2k}|} \prod_\rho \bigg( 1-\frac{2k}\rho \bigg) \bigg( 1-\frac{2k}{1-\rho} \bigg) \bigg( 1-\frac{2k+1}\rho \bigg) \bigg( 1-\frac{2k+1}{1-\rho} \bigg). $$

(2) What?

Answer by Greg Martin for Small primes in arithmetic sequences

2012-10-24T18:06:33Z

When $a=2$, the sum you want the asymptotics of is basically $$ \frac12 \frac{\log n}n \sum_{p\le n} \frac{\phi(p-1)}{p-1} \sim \frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1}, $$ which is half the average value of the multiplicative function $\phi(n)/n$ on shifted primes $p-1$. The heuristic for evaluating this constant is as follows: recall that $$ \frac{\phi(p-1)}{p-1} = \prod_{q\mid(p-1)} \bigg( 1-\frac1q \bigg). $$ For every fixed prime $q$, a proportion $1/(q-1)$ of primes $p$, namely those congruent to $1$ (mod $p$), will have $\phi(p-1)/(p-1)$ containing a factor of $1-1/q$; the others, a proportion $(q-2)/(q-1)$ of the primes, simply have the factor 1 instead. Heuristically, all these contributions are independent, and so the average value of $\phi(p-1)/(p-1)$ should be the product of the averages for each $q$, which are $$ \frac1{q-1} \bigg( 1-\frac1q \bigg) + \frac{q-2}{q-1}1 = 1-\frac1{q(q-1)}. $$ Therefore we predict that $$ \frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1} \to \frac12 \prod_q \bigg( 1-\frac1{q(q-1)} \bigg) \approx 0.186978. $$ This can be proved without much difficulty, using the method outlined in Terry's comment. EDITED TO ADD: $$ \sum_{p\le n} \frac{\phi(p-1)}{p-1} = \sum_{p\le n} \sum_{d\mid(p-1)} \frac{\mu(d)}d = \sum_{d\le n} \frac{\mu(d)}d \sum_{p\le n, p\equiv1\pmod d}1 = \sum_{d\le n} \frac{\mu(d)}d \pi(n;d,1), $$ where $\pi(x;q,a)$ is the number of primes $p\le x$ with $p\equiv a\pmod q$. Now one can use the prime number theorem in arithmetic progressions to get an asymptotic formula for $\pi(n;d,1)$ when $d$ is small and the Brun-Titchmarsh theorem to get an upper bound for $\pi(n;d,1)$ when $d$ is large. The result will be the same, in the limit, as what you get if you simply plug in $\pi(x)/\phi(d)$ for $\pi(x;d,1)$: $$ \frac12 \frac1{\pi(n)} \sum_{p\le n} \frac{\phi(p-1)}{p-1} \sim \frac12 \sum_{d\le n} \frac{\mu(d)}{d\phi(d)} \sim \frac12 \sum_{d=1}^\infty \frac{\mu(d)}{d\phi(d)} = \frac12 \prod_p \bigg( 1 + \frac{-1}{p\phi(p)} + \frac0{p^2\phi(p^2)} + \cdots \bigg). $$

Answer by Greg Martin for Bounds of weighted sums of Mangoldt function under the Riemann Hypothesis

2012-10-18T07:57:23Z

This can be found, for example, as Theorem 13.7 in Montgomery and Vaughan's Multiplicative Number Theory I. Classical Theory.

Comment by Greg Martin

2013-06-18T17:13:54Z

I imagine if one "toned down" Liouville's construction and wrote $\alpha=\sum_{n=1}^\infty 10^{-\lfloor\mu^n\rfloor}$, then one could show that $\mu(\alpha)=\mu$. There is something to be shown, though, since the obvious rational approximations by terminating decimals only demonstrate that $\mu(\alpha)\ge\mu$.

Comment by Greg Martin

2013-06-18T17:10:40Z

I'm pmretty sure $\mu(\alpha)=1$ for rational $\alpha$ is correct.

Comment by Greg Martin

2013-06-17T19:21:07Z

Just wanted to point out that if you let $J$ be the complement of $I$ in $\mathbb Z/L\mathbb Z$, then an upper bound on $|A\cap J|/|J|$ can be connected to a lower bound on $|A\cap I|/|I|$.

Comment by Greg Martin

2013-06-15T09:46:00Z

I think the answer is correct if "primitive root" is replaced by "quadratic nonresidue" everywhere.

Comment by Greg Martin

2013-06-09T00:42:36Z

I doubt anything deep lies under a formula containing $\pi(\pi(x))$ and higher compositions (even if one believes that the fractional part of the natural logarithm of something might be interesting).

Comment by Greg Martin

2013-05-29T06:00:41Z

If I understand your modified question correctly, you can construct $A_n$ that don't represent $m$ by a greedy algorithm: given $s_1,\dots,s_k$ already in $A_n$, there are $\phi(n)-k$ other possible choices for $s_{k+1}$ among invertible elements $\mod n$, and at most $2k$ of them result in the extended set representing $m$. So you can find an $A_n$ of size about $\phi(n)/3$ that doesn't represent $m$. (And $\phi(n)$ is always larger than a constant times $n/\log\log n$, so much bigger than $\log^2n$.)

Comment by Greg Martin

2013-05-28T03:12:23Z

"non-measurable cardinality"?

Comment by Greg Martin

2013-05-27T19:11:47Z

If you think your proof has insights that others would appreciate, then I encourage you to write it up and post it in an appropriate place.

Comment by Greg Martin

2013-05-23T22:17:40Z

Consider the ratio $f(k+1)/f(k)$ and figure out when it's greater than 1. That will tell you when $f(k+1)$ exceeds $f(k)$, and then you've basically isolated the minimum.

Comment by Greg Martin

2013-05-20T06:44:40Z

I think you have some misconceptions about the objects being discussed. A simplex is a pretty general object - the specific angles and side lengths aren't relevant. The barycentric subdivision of a 2-dimensional simplex (triangle) is a set of six triangles; yes, these new triangles can be right triangles, but that's not a problem.

Comment by Greg Martin

2013-05-19T00:50:49Z

I still don't think you've nailed down exactly what you mean by "nontrivial". For example, in Weyl's and Vinogradov's results, you have an assumption on $\alpha$, namely that is irrational. Why is "irrational" okay but "normal in base 2" not okay?

Comment by Greg Martin

2013-05-17T19:49:29Z

I imagine the question being asked is: what is the greatest lower bound on the largest gap between P2s up to $x$, as a function of $x$? In other words, an analogue for P2s of Rankin's result on large gaps between primes.

Comment by Greg Martin

2013-05-15T17:13:40Z

I agree that any $k+1$ people can compute $f$, using, say, Lagarange interpolation ... but, using the Chinese remainder theorem? I don't see $k+1$ different moduli here - only (mod $p$).

Comment by Greg Martin

2013-05-15T07:27:32Z

Also, this sort of question (studying college-level mathematics) is better suited for math.stackexchange.com than for here.

Comment by Greg Martin

2013-05-15T07:27:18Z

This sort of question (studying college-level mathematics) is better suited for math.stackexchange.com than for here.