Archive for October, 2010

Generalizing generalities

October 31, 2010

Theorem.
Let L_n be the least common multiple of \{1,2,..,n\} and X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{r_i}{i s_i} with r_i, s_i \in Z for all i, r_{i+m} = r_i for some m and s_{i+m'} = s_i for some m'. Then \gcd(X_n, L_n) > 1 for infinitely many n.

Proof.
It is clear that it is necessary that the numerator of X_n does not equal 1 infinitely often. So let’s start with that. Assume that the numerator of X_{n-1} does equal 1 for some large n, where n is not a prime power. Then: |X_n| + |X_{n-1}| \ge |X_n - X_{n-1}| = \left|\dfrac{L_n r_n}{n s_n}\right| > \dfrac{L_n}{n^2} > 2. And since |X_{n-1}| \le 1, we have |X_n| > 1, which is never a unit fraction. Let a be an integer for which a \ge \max(m, m', \displaystyle \max_i (|s_i|)) and p be a prime larger than a such that p divides X_a. Note that if such a prime doesn’t exist for any a, we would have that all the prime divisors of X_a (which, as we saw, exist for infinitely many a), are smaller than or equal to a. But a prime divisor of X_a which is smaller than or equal to a also divides L_a. And this would immediately imply our theorem. So we may assume the existence of a prime p > a \ge \max(m, m', \displaystyle \max_i(|s_i|)) dividing X_a. Now, let k be any (positive) multiple of lcm(\varphi(m), \varphi(m')) and set n = ap^k;

X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{r_i}{i s_i}
\equiv L_n \displaystyle \sum_{i=1}^a \dfrac{r_{ip^k}}{ip^k s_{ip^k}} \pmod{p}
\equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{r_i}{i s_i}      \pmod{p}
\equiv 0                      \pmod{p}

Another generalization

October 31, 2010

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+m} = b_i \in \aleph for all i and some m. Then \gcd(X_n, L_n) > 1 necessarily happens infinitely often.

Proof.
Assume a p > a exists that divides X_a = L_a \displaystyle \sum_{i=1}^a \dfrac{b_i}{i} for some a \ge m. Note that we may assume so, because if such a p doesn’t exist, we’re immediately done since every primedivisor of X_a must then be smaller than or equal to a and thus also be a divisor of L_a. Let k be any multiple of \varphi(m) and n = ap^k. We then have:

X_n = L_n \displaystyle \sum_{i=1}^n \dfrac{b_i}{i} \equiv L_n \displaystyle \sum_{i=1}^a \dfrac{b_{ip^k}}{ip^k} \equiv \dfrac{L_n}{p^k} \displaystyle \sum_{i=1}^a \dfrac{b_i}{i} \equiv 0 \pmod{p}

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.

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\}