10
$\begingroup$

What is the largest possible numerator when put in reduced form over all sums of the form $$\sum_{k=1}^n\frac{c(k)}{k}$$ where $c(k)\in\{-1, 0, 1\}$? An easy bound is to consider what happens when we don't reduce the fraction. Then we have that if $L$ is the $\text{lcm}$ over all $k$ such that $c(k)\neq 0$, then $$\Big|\text{num}\left(\sum_{k=1}^n\frac{c(k)}{k}\right)\Big|\le \Big|L\sum_{k=1}^n\frac{c(k)}{k}\Big|\le L\sum_{k=1}^{n}\frac{|c(k)|}{k}\le H_n\text{lcm}(1,\dots,n)$$ where $H_n$ is the $n$-th harmonic number. For some $n$, this bound is the best achievable, which can be seen when the denominator of $H_n$ truly is $\text{lcm}(1,\dots, n)$. Can any improvements be made or can this be shown to be the best bound for certain subsets of numbers? Another useful result would be the asymptotics of this, even if for only certain subsets.
This problem came from considering this problem involving egyptian fractions.

$\endgroup$

1 Answer 1

2
$\begingroup$

To answer this question, I'm going to use some ideas that will also be present in a (hopefully) forthcoming paper of mine on somewhat related questions on harmonic sums. I will make repeated (ab)use of the prime number theorem and little-o notation, $p$ always denotes a prime number, and if anything is unclear, please feel free to ask.

The idea is that we initially choose $c(k) = 1$ for all $k$, and then change some $c(k)$ to $0$ if it turns out that the denominator of $\displaystyle \sum_{k=1}^n \frac{c(k)}{k}$ does not equal $L_n := lcm(1, \ldots, n)$. The end result is that we can get quite close to your upper bound. More precisely, we have the following theorem.

Theorem. It is possible to choose $c(k) \in \{0,1\}$ (for $1 \le k \le n$) such that the numerator of $\displaystyle \sum_{k=1}^n \frac{c(k)}{k}$ is bigger than $L_n \left(H_n - \frac{1+o(1))}{\log^2(n)}\right)$.

Proof. Define $X_n = L_n \displaystyle \sum_{k=1}^n \frac{c(k)}{k}$. Then we want $\gcd(X_n, L_n) = 1$ (so that $L_n$ truly is the denominator of the sum) and $X_n$ as big as possible. To ensure $\gcd(X_n, L_n) = 1$, we need that $X_n$ is not divisible by a prime $p \le n$. So let $p \le n$ be a prime and assume for now for simplicity that $p > \sqrt{n}$. Then, after initially choosing $c(k) = 1$ for all $k$, let us look at $X_n \pmod{p}$, by noting that $\frac{L_n}{k} \neq 0 \pmod{p}$ precisely when $p|k$;

\begin{align*} X_n &= \displaystyle \sum_{k=1}^n \frac{L_n}{k} \\ &\equiv \frac{L_n}{p} + \frac{L_n}{2p} + \ldots + \frac{L_n}{lp} \pmod{p} \end{align*}

with $l = \left \lfloor \frac{n}{p} \right \rfloor$.

If we are unlucky then the above sum is $0 \pmod{p}$. But then we just choose $c(lp) = 0$ to change the value of $X_n \pmod{p}$ to something non-zero.

In general (when $p$ is possibly smaller than $\sqrt{n}$) let $p^m$ be the largest power of $p$ with $p^m \le n$. Then $\frac{L_n}{k} \neq 0 \pmod{p}$ precisely when $k$ divides $p^m$. And with $l = \left \lfloor \frac{n}{p^m} \right \rfloor$, if $X_n \equiv 0 \pmod{p}$ with all $c(k) = 1$, then simply choose $c(lp^m) = 0$ and we are fine again.

Another thing to note is that, with $c(lp) = 1$ for all $l$, when $p \ge \frac{(1+o(1))n}{\log(n)}$, the inequality $X_n \pmod{p} \neq 0 \pmod{p}$ is guaranteed by the fact that in that case $X_n \equiv \dfrac{L_n}{p} \displaystyle \sum_{k=1}^l \frac{1}{k} \equiv 0\pmod{p}$ if and only if the numerator of $\displaystyle \sum_{k=1}^l \frac{1}{k}$ is divisible by $p$. But this numerator is smaller than $L_lH_l < e^{(1+o(1))l} \le p$, so definitely not divisible by $p$. This means that if we have to change $c(lp)$ to $0$ for some $p$ with $\sqrt{n} < p \le n$, then $p < \frac{(1+o(1))n}{\log(n)}$ and from this it follows $lp > n - \frac{(1+o(1))n}{\log(n)}$.

In conclusion we may say that we can simply choose $c(k) = 1$ for all $k$, except for some $k$ of the form $k = lp^m$ where we may have to choose $c(k) = 0$. So either $p \le \sqrt{n}$ (in which case $k > \frac{n}{2}$) or $\sqrt{n} < p < \frac{(1+o(1))n}{\log(n)}$ and $k > n - \frac{(1+o(1))n}{\log(n)}$. Let us denote $\left \lfloor \frac{(1+o(1))n}{\log(n)} \right \rfloor$ by $x$.

We can now calculate a lower bound on $X_n$.

\begin{align*} X_n &= L_n \sum_{k=1}^{n} \frac{c(k)}{k} \\ &\ge L_n \left(\sum_{k=1}^{n} \frac{1}{k} - \sum_{k=n-x+1}^{n-x+\pi(x)} \frac{1}{k} - \sum_{k = \left \lfloor \frac{1}{2}n \right \rfloor + 1}^{\left \lfloor \frac{1}{2}n \right \rfloor + \pi(\sqrt{n})} \frac{1}{k}\right) \\ &> L_n \left(\sum_{k=1}^{n} \frac{1}{k} - \frac{\pi(x)}{n-x} - \frac{2\pi(\sqrt{n})}{n}\right) \\ &= L_n\left(H_n - \frac{1+o(1)}{\log^2(n)}\right) \end{align*}

And the proof is finished.

If one is more interested in explicit bounds, one can without too much trouble use explicit estimates on prime counting functions to prove, for example, $X_n > L_n \left(H_n - \frac{4}{\log^2(n)} \right)$ for all $n \ge 2$.

In the other direction, looking at $X_n \pmod{3}$, for $n = 3^{m+1}-1$ one needs $c(3^{m})$ or $c(2\cdot3^{m})$ to be $0$ (or $-1$), or else have $X_n \le \frac{1}{3}L_nH_n$. So $X_n \le L_n \left(H_n - \frac{3}{2(n+1)} \right)$ infinitely often. With a bit of work one can show a very modest improvement to $X_n < L_n \left(H_n - \frac{2}{n}\right)$ infinitely often, by finding infinitely many $n$ such that there exist $m_1, m_2 \in \mathbb{N}$, for which simultaneously $2\cdot3^{m_1} \le n < 3^{m_1+1}$ and $4\cdot5^{m_2} \le n < 5^{m_2+1}$. No doubt for every $c > 0$ there are infinitely many $n$ such that $X_n < L_n \left(H_n - \frac{c}{n}\right)$ holds, and maybe some pigeonhole type argument could give us that, but as of now I do not see how.

$\endgroup$
6
  • $\begingroup$ I think there might be some problems in the logic of adjusting some $c(k)$'s to zero, as changing one value to zero influences which new primes divide it. I'd have to think more, but one objection is that given two primes $p_1$ and $p_2$, say $p_1\mid X_n$ and $p_2\nmid X_n$. Thus we set $c(l_1p_1)=0$, but then say doing this causes $p_2\mid X_n$ so we go to set $c(l_2p_2)=0$. What happens if $l_1p_1=l_2p_2$ and thus we already have $c(l_2p_2)=0$ meaning we must adjust a lower value? $\endgroup$ Aug 20, 2019 at 18:24
  • $\begingroup$ My instinctual objection is that we can't just go through each prime and adjust each $c(k)$ to zero, because each adjustment changes what new primes now divide it, so there's no guarantee of termination that's simpler than the original problem. $\endgroup$ Aug 20, 2019 at 18:28
  • $\begingroup$ Great question! I should have addressed this. Note that we only ever possibly change $c(k)$ to $0$ if $k = lp^m$ with $1 < l < p$ and such that $p^{m+1} > n$. I claim that changing this $c(k)$ does not change the value of $X_n \pmod{q}$ for any other prime $q \le n$. Analogous to what saw before, looking at $X_n = \sum_{k=1}^n \frac{L_nc(k)}{k} \pmod{q}$, the only terms in the sum which are non-zero mod $q$ are where $k$ can be written as $l'q^{m'}$ with $1 \le l' < q$ and where $q^{m'}$ is such that $q^m \le n < q^{m+1}$. (cont) $\endgroup$
    – Woett
    Aug 20, 2019 at 18:39
  • $\begingroup$ But $k$ can never both be equal to $lp^m$ and $l'q^{m'}$ as otherwise $q^{m'} | l$ and $p^m | l'$ by unique factorization and we would get the contradictory string of inequalities $l \ge q^{m'} > l' \ge p^m > l$. So for every prime $p$ we change at most one value $c(k)$ to $0$, and this change does not affect $X_n \pmod{q}$ for any prime $q \le n$ different from $p$. $\endgroup$
    – Woett
    Aug 20, 2019 at 18:42
  • $\begingroup$ Also if $k=lp^m$ don't we only have $k>n-\left(\frac{(1+o(1))n}{\log(n)}\right)^m$? $\endgroup$ Aug 21, 2019 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.