G-g-generalize

October 29, 2010

I never meant for it to happen. It violates all intentions of this blog to generalize a theorem. So I’d like to blame Ernie Croot for the suggestion;

Let B be any (unordered) set of integers. Let L_n be the least common multiple of \{1,2,..,n\} and X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{b_i}{i}, where b_i \in B for all i. Then \gcd(X_n, L_n) > 1 necessarily happens infinitely often in exactly 2 cases: there either exists an odd prime p for which b_i \equiv b_j \pmod{p} for all b_i, b_j \in B, or all the b_i are even. And it’s not even necessary to start the sum at i = 1.

Advertisements

Another random conjecture

October 28, 2010

In spirit of yesterdays post, could the following be true, wild as it is?;

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p} implies n \le n_p

If true, n_p = O(p^p) can’t be far from the truth. Do we have n_p = O(p^k)? I very much doubt it.. n_3 = 22, n_5 = 24 and n_7 \ge 16735 \approx 7^5 in any case.

EDIT: By just googling “harmonic number 16735” I found some articles from around 1990, that are devoted to exactly this conjecture and it seems like it’s true (it’s proven for all p < 550 with the possible exception of 83, 127 and 397), but hard. The only remaining conjecture from the previous post seems to hold up too. Anyway, they use p-adic methods, which I am (still) not that familiar with, so I’m definitely going to search for some literature about it.

Three random conjectures

October 28, 2010

Please refute at least one of the following:

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p^2} implies n < p^2

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p^3} implies n = p - 1

\displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv 0 \pmod{p^4} never happens

EDIT. p = 11, n = 10583 is quite a cute counterexample to the first 2 of these.

Two (happy) notes on unit fractions

October 26, 2010

After some encouragement of Ernie Croot (yes, the man that proved the Erdös-Grahamproblem), I managed to find the following generalization of an earlier shown theorem;

Let n and m be any given natural numbers and p be a given prime. Let a \in \aleph be the unique number not divisible by p and smaller than p^m for which a k \in \aleph_0 exists such that ap^k is the closest underapproximation of n possible**. Let L_n be the least common multiple of the first n natural numbers and let X_n be such that \dfrac{X_n}{L_n} = \displaystyle \sum_{i=1}^n \dfrac{1}{i}. Then: p^m divides X_n if, and only if, p^m divides X_a.

On another happy note, on Wolfram Mathworld I found the following conjecture (slightly generalized by myself):

Let D_n be the number of digits of the denominator of the n-th harmonic number, written in base b. Then: \dfrac{n}{D_n} converges to \log{b}.

And I think the best application of everything I have been able to show so far concerning the problems of Erdös and Graham, is an easy proof of the above (sweet!) conjecture 🙂

** Since this definition might be vague, here are some examples:
If n = 100, p = 7 and m = 1, we have a = 2 
(2*7^2 = 98 \le 100). So our theorem says 7 | X_{100} iff 7 | X_2, which is not the case.
If n = 100, p = 7 and m = 3, we have a = 100
(100*7^0 = 100 \le 100). So our theorem says 7^3 | X_{100} iff 7^3 | X_{100}, which is not the case.
If n = 100, p =5 and m = 2, we have a = 4 (4*5^2 = 100 \le 100). So our theorem says 5^2 | X_{100} iff 5^2 | X_4, which is the case. In general we have (assuming n > p^m, otherwise a would just equal n and our theorem then trivializes):
k = \left\lfloor\log_p{n}\right\rfloor - m + 1,
a' = \left\lfloor\dfrac{n}{p^k}\right\rfloor and
a = \dfrac{a'}{(a', p^m)}

Summary

October 22, 2010

If you haven’t read everything I wrote last week, but would still like to solve an Erdös-Graham-problem or two with me, here is, basically, everything I know so far:

Let n be a given natural number and p be a prime smaller than n. Let a \in \aleph be the unique number smaller than p such that ap^k \le n < (a+1)p^k holds for some k \in \aleph_0. Let L_n be the least common multiple of \{1,2,..,n\} and X_n be such that \dfrac{X_n}{L_n} = \displaystyle \sum_{i=1}^n \dfrac{1}{i}. And, at last, let u_{y,z} and v_{y,z} be coprime positive integers, such that, for y,z \in \aleph\displaystyle \sum_{i=y}^z \dfrac{1}{i} = \dfrac{u_{y,z}}{v_{y,z}}. Then:

\text{ }

1) p | X_n,  p | X_a and p | X_{p-1-a} are all equivalent

2) If p > (1 + o(1))\dfrac{n}{\log{n}}, then p does not divide X_n

3) If n is not a prime power, X_n \neq X_{n-1} \pmod{p} implies n = ap^k

4) For every fixed y, there is a z \le 6y, for which v_{y,z} < v_{y,z-1}

\text{ }

Btw, one of the problems is: prove or disprove that the greatest common divisor of X_n and L_n is equal to 1 for infinitely many n. Another one is to find the smallest (or at least a better upper bound for) z = z(y), such that v_{y,z} < v_{y,z-1}.

More sensible heuristics

October 20, 2010

If you’re 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 difference that not a lot of people participate 😛 Hopefully that’ll change though. Anyway, the heuristics and assumptions in the previous post may seem a bit weird, so I try to make things more senseful  here; let n be given. Assume a_ip_i^{k_i} \le n < (a_i+1)p_i^{k_i} with 1 \le a_i < p_i and where the p_i run over all primes such that 2 < p_i < n. Then g_n = 1 if, and only if p_i does not divide X_{a_i} for all i. Let f(p) be the amount of a for which a < p and p | X_a (so f(p) is the function we want an decent upper bound on). Then the ‘chance’ that p doesn’t divide X_n (assuming for simplicity that P(a_i = x) = \dfrac{1}{p-1} for all x, 1 \le x \le p-1), equals  \dfrac{p - 1 - f(p)}{p - 1}. The reasonable assumption (and possibly not even that hard to make rigorous) seems that a_i and a_j are independent for i \neq j. So the ‘chance’ that p_i does not divide X_{a_i} for all i, should be \displaystyle \prod_{2 < p_i < n} \left(1 - \dfrac{f(p)}{p-1}\right).  And if we have a good upper bound on f(p), say f(p) = O(\log p), then we should be able to show that this product doesn’t go to 0 fast enough to prevent g_n = 1 from happening.

A proof of the aforementioned theorem and ideas about some sort of probabilistic proof of the infinitude of n for which g_n = 1

October 20, 2010

If you already have no idea what I’m talking about; please read the last 4 posts.

Let n = ap^k with 2 \le a \le p-1. Then we have p | X_n if, and only if X_{n-1} + \dfrac{L_n}{n} \equiv 0 \pmod{p};

X_{n-1} + \dfrac{L_n}{n} \equiv L_n \displaystyle \sum_{i=1}^{n-1} \dfrac{1}{i} + \dfrac{L_n}{n} \pmod{p}
\equiv L_n \displaystyle \sum_{i=1}^n \dfrac{1}{i} \equiv L_n \displaystyle \sum_{i=1}^a \dfrac{1}{ip^k} \pmod{p}
\equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{1}{i} \equiv \dfrac{L_n}{p^k}\dfrac{X_a}{L_a} \pmod{p}

And this is equal to 0 \pmod{p} if, and only if X_a \equiv 0 \pmod{p}. And this suffices to prove the theorem I mentioned in the previous post. And, by Wolstenholme´s theorem, we know that p | X_{p-1} for all p \ge 3. So for every number n, for which (p-1)p^{k-1} \le n < p^k holds, we have that p | X_n. Assume for the moment that the following converse holds: a = p-1 is the only a for which p | X_a.  While this is not true (a = 3p = 11 is a counterexample), there should be a relatively low upper bound for the amount of a with a < p and p | X_a. In any case, bear with me for the moment. Let’s pick some ‘random’ number m and let’s assume that it lies pretty much in the middle of two consecutive powers of p. Then, the amount of numbers n, with n < m and for which p | X_n, is roughly equal to \dfrac{2m}{(p-1)^2}.  Now the sweet part: if we sum over all primes < m, then what we obtain is not more than the number of n such that X_n is divisible by any prime < m. And \displaystyle \sum_{p=3}^m \dfrac{2m}{(p-1)^2} < \displaystyle \sum_{p=3}^\infty \dfrac{2m}{(p-1)^2} \approx 0.75m. So at least about 25% of all the X_n with n < m is not divisible by any prime < m, which implies g_n = (X_n, L_n) \le (X_n, L_m) = 1.

Obviously, this doesn’t come very close to a real proof. But it might be a good heurstic start. Anyway, it certainly seems necessary to have some bounds on the a for a given p, such that a < p and p | X_a. Let me know what you think!

More on unit fractions, greatest common divisors, least common multiples and such

October 19, 2010

Just a quick update, I’ll elaborate later. The technique I used 2 posts ago, in proving that g_n > 1 infinitely often, can be quite easily generalised and yield a lot more that way. And it also gives some insight in why it’s hard to show g_n = 1 infinitely often; maybe it’s not true! The theorem I will prove later (either today or tomorrow) will be:

Let n be a given natural number and p be a given prime. Let a \in \aleph be the unique number smaller than p such that ap^k \le n < (a+1)p^k for some k \in \aleph_0. Then the following two are equivalent:

1) p | X_n
2) p | X_a

Where \dfrac{X_n}{L_n} = \sum_{i=1}^n \dfrac{1}{i}, with L_n the least common multiple of \{1,2,..,n\}

Solving a second Erdos-problem (!!)

October 19, 2010

Again: not happy about this post. It seems like I’m terrible at explaining my thoughts on paper. Well, it’s not as if I didn’t know that, but it’s worse than I thought. Anyway, solving two problems of Erdos and Graham in 24 hours is not something I’m not going to blog about;

In their book, Erdös and Graham also ask the following, I think more general, question:

Let \displaystyle \sum_{i=a}^b \dfrac{1}{i} = \dfrac{u_{a,b}}{v_{a,b}}. For fixed a what is the least b = b(a) such that v_{a,b} < v_{a,b-1}? In fact, is there always such a b for every a? Using the result of the previous post, I am able to show that b exists for every a, and, even more, b \le 6a for all a. In a very strict sense this is best possible, as b(1) = 6. I will use the notation from the previous two posts, along with the new definition: X_{a,b} = X_b - X_{a-1}*\dfrac{L_b}{L_{a-1}}. We now have:

\displaystyle \sum_{i = a}^b \dfrac{1}{i}  
= \displaystyle \sum_{i = 1}^b \dfrac{1}{i} - \displaystyle \sum_{i = 1}^{a-1} \dfrac{1}{i}
= \dfrac{X_b}{L_b} - \dfrac{X_{a-1}}{L_{a-1}}
= \dfrac{X_{a,b}}{L_b}

With v_{a,b} = \dfrac{L_b}{(X_{a,b}, L_b)}. Now, let k be such that 3^k \le a < 3^{k+1}. Let b = 2*3^{k+1}. Note that L_b = L_{b-1} in that case. So we’re done if we can show (X_{a,b}, L_b) > (X_{a, b-1}, L_{b-1}). And the proof of this is not very hard using the result of the previous post;

(X_{a, b}, L_b) = (X_b - X_{a-1} \dfrac{L_b}{L_{a-1}}, L_b) = (X_{b-1} + \dfrac{L_b}{b} - X_{a-1} \dfrac{L_b}{L_{a-1}}, L_b)

Now, the only difference with (X_{a, b-1}, L_{b-1}) is the term \dfrac{L_b}{b}. This term doesn’t affect anything, except for possibly factors of 2 and 3 (since b = 2*3^k). But we already know that X_n is odd for all n, which implies X_{a,b} is also odd for all a,b with b \ge 2a. So the only thing that the term \dfrac{L_b}{b} might change, is the divisibility of X_{a,b} by 3. And, indeed, we showed in the previous two posts that (X_{b-1}, 3) = 1 for b = 2*3^k, while (X_b, 3) = 3. So, since 3|\dfrac{L_b}{L_{a-1}} by our choice of b, (X_{a, b-1}, 3) = 1, while (X_{a,b}, 3) = 3. In other words: 3v_{a,b} \le v_{a, b-1}, and this finishes our proof.
To recapture: Let a be fixed. Let k be such that 3^k \le a < 3^{k+1}. Choose b = 2*3^{k+1}. Then: v_{a,b} < v_{a,b-1}

Solving an Erdos-problem (!)

October 19, 2010

Alright, I answered one of the questions asked in the previous post in the affirmative; Let L_n be the least common multiple of \{1, 2, .., n\}. Let X_n = L_n \sum_{i=1}^n \dfrac{1}{i}. Let g_n be the greatest common divisor of L_n and X_n

Question: Does g_n > 1 happen infinitely often?

Answer: Yes!

Proof.
First of all, if n is not a prime power, there are 2 possibilities: Either X_n \equiv X_{n-1} \pmod{p}, or n = ap^k, with 2 \le a \le p - 1; We have X_n = X_{n-1} + \dfrac{L_{n-1}}{n} and \dfrac{L_{n-1}}{n} is always divisible by p, unless n = ap^k, with a \le p-1. Furthermore, since statement 2) in the previous post implies that for n a power of 3 we have (g_n, 3) = 1, we actually have (g_n, 3) = 1 for every n with 3^k \le n \le 2*3^k - 1. We shall show that (g_n, 3) = 3 for n = 2*3^k, which implies that for every n with 2*3^k \le n \le 2*3^{k+1} - 1. And, clearly, there are infinitely many of them.

Let everything be defined as above, let n = 2*3^k and let (y, z) be the greatest common divisor of y and z. Since L_{n-1} = L_n, we have that X_n = X_{n-1} + \dfrac{L_n}{n}. Since (\dfrac{L_n}{n}, 3) = 1 by the definition of n and (X_{n-1}, 3) = 1, we have that \dfrac{L_n}{n} and X_{n-1} must be equal modulo 3 (because if they’re different, then their sum, which equals X_n, must be divisible by 3, in which case we’re done). So we have:

\dfrac{L_n}{n} \equiv X_{n-1} \equiv L_{n-1} \sum_{i=1}^{n-1} \dfrac{1}{i} \equiv L_n \sum_{i=1}^{n-1} \dfrac{1}{i} \pmod{3}

But every term except \dfrac{1}{3^k} in the last sum vanishes modulo 3;

\dfrac{L_n}{2*3^k} = \dfrac{L_n}{n} \equiv L_n \sum_{i=1}^{n-1} \dfrac{1}{i} \equiv \dfrac{L_n}{3^k} \pmod{3}

Multiplying by 2 gives the impossible conclusion:

\dfrac{L_n}{3^k} \equiv 2 * \dfrac{L_n}{3^k} \pmod{3}

So we must have that \dfrac{L_{n-1}}{n} and X_{n-1} are different (while both non-zero) modulo 3. So their sum, better known as X_n, is divisible by 3. Q.E.D.