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 = 3$$p = 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\}$