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

## 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?

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.