Investigating an Erdös-problem

Apologies in advance; I’m not entirely happy about this post. I should have made everything clearer, but somehow that’s hard for me. Anyway, I hope you’re able to understand everything anyway, although it might take you two tries to get what I’m clumsily trying to articulate. As always, if you have any questions, ask me. And if you have any ideas on how to further attack the problem I’m talking about, tell me! Thanks, and enjoy.

Let L_n be the least common multiple of \{1, 2, .., n\} and let X_n = L_n \sum_{i=1}^n \dfrac{1}{i}. Erdos and Graham were interested in (L_n, X_n); the greatest common divisor of L_n and X_n, let’s call it g_n. They posed, among many, many more, the following questions (here, page 30 in the pdf-file): Does g_n = 1 hold for infinitely many n? Does g_n > 1 hold infinitely often? Clearly, these questions seem too easy to not attack, so I went for it. So far I tried to get a feeling for the way g_n behaves, by comparing it to g_{n-1} and see what can happen for various n. I have managed to find the following truths (where p always denotes a prime):

1) g_p = g_{p-1}.
2) g_{p^k} = \dfrac{g_{p^k - 1}}{(X_{n-1}, p^{k-1})} (a clear generalization of 1)).
3) if for every prime p that divides n,  png_n| L_n holds, then g_n = g_{n-1}.
4) (implied by 3, but, for me, a lot easier to grasp)
If (n, X_n) = 1 and n can’t be written as n = ap^k with a \le p - 1, then g_n = g_{n-1}.
5) If n can’t be written as n = ap^k with a \le p - 1, then g_n = 1 if, and only if, g_{n-1} = 1.
6) X_n is odd

Proofs.
In general we have the following:

\dfrac{X_{n-1}}{L_{n-1}} + \dfrac{1}{n} = \dfrac{nX_{n-1} + L_{n-1}}{nL_{n-1}} = \dfrac{\dfrac{n}{(n, L_{n-1})}X_{n-1} + \dfrac{L_{n-1}}{(n, L_{n-1})}}{L_n}
So X_n = \dfrac{nX_{n-1}+ L_{n-1}}{(n, L_{n-1})}. While this may seem messy, it really isn’t;  (n, L_{n-1})  easily simplifies in any case; if n is not a prime power, it simplifies to n and if n = p^k, it simplifies to p^{k-1}.

Proof of 2).
Let n = p^k. Now: g_n = (X_n, L_n) = (pX_{n-1} + \dfrac{L_{n-1}}{p^{k-1}}, pL_{n-1})
= (pX_{n-1} + \dfrac{L_{n-1}}{p^{k-1}}, p^{k+1}X_{n-1}) = (pX_{n-1} + \dfrac{L_{n-1}}{p^{k-1}}, X_{n-1})
= (\dfrac{L_{n-1}}{p^{k-1}}, X_{n-1}) = \dfrac{g_{n-1}}{(X_{n-1}, p^{k-1})}

Proof of 3).
Let X_n' = \dfrac{X_n}{g_n}, L_n' = \dfrac{L_n}{g_n}. Now, since pn | L_n, n can’t be a prime power. In particular: L_n = L_{n-1}. So:

g_n = (X_n, L_n) = (X_{n-1} + \dfrac{L_{n-1}}{n}, L_{n-1}) =(X_{n-1} + \dfrac{L_{n-1}}{n}, nX_{n-1})
=g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, nX_{n-1}') = g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, n).

Let p be a prime such that p | n. Then, by assumption, p| \dfrac{L_{n-1}'}{n}. So if p is a divisor of g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, n), p must divide X_{n-1}'. But (X_{n-1}', L_{n-1}) = 1! And since p | L_{n-1}, this is impossible. So g_n = g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, n) = g_{n-1}(X_{n-1}' + \dfrac{L_{n-1}'}{n}, 1) = g_{n-1}.

Proof of 4).
If n isn’t expressible as ap^k with a \le p-1, then, equivalenty, n = ap^k implies a > p. So In particular p^{k+1} < n, which implies p^{k+1} | L_n. So pn | L_n for every p | n. Furthermore g_n trivially divides L_n and if (n, g_n) = 1, as we assumed, png_n | L_n must hold. So we may use 3) to show g_n = g_{n-1}

Proof of 5).
Assume n can’t be written as n = ap^k with a \le p-1. And since we already covered prime powers, let’s assume n isn’t a prime power either. Now: g_n = (X_n, L_n) = (X_{n-1} + \dfrac{L_{n-1}}{n}, L_{n-1}). If g_{n-1} = 1, then there is no prime that both divides X_{n-1} and L_{n-1}. But every prime that divides L_{n-1}, also divides \dfrac{L_{n-1}}{n}. So g_n must equal 1 too. On the other hand, if g_{n-1} > 1, then a prime p_1 exists that divides both X_{n-1} and L_{n-1}. And again, every prime that divides L_{n-1}, also divides \dfrac{L_{n-1}}{n}. So now g_n must be at least p_1 > 1.

Proof of 6).
Easy exercise 🙂

Advertisements

One Response to “Investigating an Erdös-problem”

  1. More sensible heuristics « Woett's Blog Says:

    […] not familiar with the problem I’m semipublicly trying to solve, please start reading here. Coming to think about it, this is basically just another polymath-project. With the only […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: