21
$\begingroup$

As usual I expect to be critisised for "duplicating" this question. But I do not! As Gjergji immediately notified, that question was from numerology. The one I ask you here (after putting it in my response) is a mathematics question motivated by Kevin's (O'Bryant) comment to the earlier post.

Problem. For any $\epsilon>0$, there exists an $n$ such that $\|n/\log(n)\|<\epsilon$ where $\|\ \cdot\ \|$ denotes the distance to the nearest integer.

In spite of the simple formulation, it is likely that the diophantine problem is open. I wonder whether it follows from some known conjectures (for example, Schanuel's conjecture).

$\endgroup$
6
  • 1
    $\begingroup$ Hi, Wadim. Let me just mention Ramanujan's trick for producing a sequence of new world records, I think Erdos and Alaoglu (spelling?) called the process champion numbers, anyway the original were Ramanujan's "superior highly composite numbers," a subsequence of the highly composite numbers but with an explicit recipe. $\endgroup$
    – Will Jagy
    Jun 14, 2010 at 3:45
  • $\begingroup$ The real question is whether you can bound your $n$ in terms of $\epsilon$. My memory --- it's been a while --- is that for certain desired bounds, there is a finite list of "good" approximations, 163 being the largest. $\endgroup$ Jun 14, 2010 at 15:55
  • $\begingroup$ If you follow the solution below, you'll find that the one can bound $n$ by means of $\epsilon$. 163 is not the largest (because the largest does not exist!) but you could also check Kevin O'Bryant's computation in the preceding Q. $\endgroup$ Jun 14, 2010 at 16:04
  • $\begingroup$ Er, my memory is wrong, anyway. And yes, for the solution below the bound is definitely there, but it grows super fast. My point was to propose a revised question: for some prescribed bound $n \lesssim f(\epsilon)$, is it true that there is an $n$ with $\| n/\log n\| < \epsilon$? How good of a bound can we get? $\endgroup$ Jun 14, 2010 at 17:16
  • 4
    $\begingroup$ Therefore, a reasonable revised problem is to get especially small values of $$ \frac{\parallel \frac{n}{ \log n} \parallel}{\left( \frac{1}{ \log n} - \frac{1}{ \log^2 n} \right)} \; \; \; \; \sim \; \; \; \; \parallel \frac{n}{ \log n} \parallel \cdot \log n $$ $\endgroup$
    – Will Jagy
    Jun 14, 2010 at 18:07

3 Answers 3

42
$\begingroup$

If $f(x)=\frac{x}{\log x}$, then $f'(x)=\frac{1}{\log x} - \frac{1}{(\log x)^2}$, which tends to zero as $x\rightarrow \infty$. Choose some large real number $x$ for which $f(x)$ is integral. Then the value of $f$ on any integer near $x$ must be very close to integral.

$\endgroup$
6
  • $\begingroup$ So, if we can choose a sequence of $x$'s whose distance to $\mathbb Z$ decreases, then we have the desired result. (Maybe, you wish to use in some way the fact that $f$ is contraction, but then it's still non-obvious to me, so please expand your argument or let me to think more.) How to guarantee that $x$ is close to an integer? This would refer to arithmetic properties of Lambert-like ($W$) function which are not even conjecturally studied... $\endgroup$ Jun 14, 2010 at 4:18
  • 5
    $\begingroup$ Let $[ ]$ denote the ceiling function. Fix $\epsilon>0$. Choose a real number $x$ so that $f(x)\in \mathbb{Z}$ and choose it large enough so that $\frac{1}{\log x} - \frac{1}{(\log x)^2}<\epsilon$. Then one can show $||f([x])||<\epsilon$ by combining the Mean Value Theorem with the fact that $|x-[x]|<1$. $\endgroup$ Jun 14, 2010 at 4:33
  • 1
    $\begingroup$ In fact, taking that $x_0$ such that $ f(x_0) = k \in Z,$ with $ 0 < f'(x_0) < \epsilon,$ and writing $ n < x_0 < n+1,$ we get $ k < f(n+1) < k + \epsilon $ and then $ k - \epsilon < f(n) < k.$ $\endgroup$
    – Will Jagy
    Jun 14, 2010 at 4:44
  • $\begingroup$ Excellent! I am happy to see how the numerological problem is demustified. Thank you very much, Kevin! I was far from the internet, but your argument is indeed very clear. Sorry for asking you more details. $\endgroup$ Jun 14, 2010 at 7:41
  • 1
    $\begingroup$ I ought to have said, with $ n < x_0 < n+1,$ that we demand $0 < f'(n) < \epsilon,$ as $ f''(x) < 0 $ when $ x > e^2.$ The numerology question stands, when do we get especially small $ k - f(n) $ or $ f(n+1) - k.$ With my choice of symbols, we could simply ask when either $ x_0 - n$ or $n+1 - x_0$ is small. This formulation takes the size of $f'$ out of the discussion. $\endgroup$
    – Will Jagy
    Jun 14, 2010 at 15:46
14
$\begingroup$

[Edited mostly to extend the computation from $1.5 \cdot 10^{13}$ to a bit over $2^{50} > 10^{15}$ and give the heuristics for expected number of records for $\| r(n) \|$ vs. $\log n \cdot \| r(n) \|$]

Just ran across this. I see that Kevin's answer completely settles the original question, but meanwhile Will Jagy raised the question of finding new record lows for $$ \log n \cdot \left\| \frac{n}{\log n} \right\| $$ and proving their infinitude. I next outline a proof that there are infinitely many such record lows, and then report on a computation of all such $n$ up to $1.5 \cdot 10^{13}$.

For the infinitude: Since $r(n) := n / \log n$ can never be an exact integer, it is enough to prove that for each $\epsilon > 0$ there exist infinitely many solutions of $\| r(n) \| < \epsilon/\log n$. In fact it's not hard to show that $\| r(n) \|$ can get as small as some negative power of $n$, because $r(n)$ is almost linear (its second derivative is $o(n^{-1})$ as $n \rightarrow \infty$) and we can choose $n_0$ to make $r'(n_0)$ as far as possible from any rational number. If I did this right, we can find intervals $|n - n_0| \leq h$ in which $\min_n \| r(n) \| \ll h^{-1}$ where $h^{-1} = |r''(n_0)|^{1/3} \sim (n_0 \log^2 n_0)^{-1/3}$. For instance, we may choose $n_0$ so that $r'(n_0) = 1 / (k + \sqrt 2)$ for $k = 1, 2, 3, \ldots$ [that is, so that $\log n_0$ solves the quadratic equation $\lambda^2 = (k+\sqrt2) (\lambda-1)$]. On such an interval, $r(n)$ is approximated by $r(n_0) + r'(n_0)(n-n_0)$ to within $O(r''(n_0) (n-n_0)^2) = O(h^2/h^3) = O(h^{-1})$, and (since $h$ grows much faster than $k$) the arithmetic sequence with common difference $r'(n_0)$ is close enough to being equidistributed that it comes within $O(1/h)$ of an integer. [We probably expect that $\| r(n) \|$ is random enough that it gets as small as $c/n$ or even $o(1/n)$, but proving such a result must be well out of reach.]

For the numerical search, the problem is quite similar to MO.19170 on nearly-integral values of $\log_{10} n!$ (since $n/ \log n$, like $\log_{10} n!$, is nearly linear in $n$). Again it takes time only $\tilde O(N^{2/3})$ to find all examples with $n < N$ using a linear-approximation technique such as described at the bottom of page 15 of Lefèvre's slides. This is actually the same idea as in the previous paragraph: partition $[1,N]$ into intervals $|n-n_0| \leq h \sim (n_0 \log^2 n_0)^{1/3}$; in general $r'(n_0)$ might be so close to a rational number that equidistribution fails, but we can still use continued fractions to find all $n$ in that interval for which $\|r(n)\| \ll h^{-1}$.

I ran this with $N = 2^{50} > 10^{15}$ on ten alhambra heads. Most finished in under two days; two took an extra day or two, probably spending most of them on $n_0$ for which $r'(n_0)$ was nearly rational (in this case one can do much better than trying every $n \in [n_0-h,n_0+h]$ for which $\| r(n_0) + r'(n_0)(n-n_0) \|$ is small, but I didn't take the extra time to implement that refinement). The computation found fourteen new records beyond the 12 initial terms 2, 17, 163, 715533, 1432276, 6517719, 11523158, 11985596, 24102781, 254977309, 451207448, 1219588338 of OEIS sequence A178806, namely

2048539023, 10066616717, 42116139191, 47657002570, 73831354169, 122478947521, 143949453227, 3152420311977, 5624690531099, 14964977749017, 25999244327633, 92799025313425, 164330745650026, and 604329910739082.

There is also a new example, namely $n = 3040705645816$, of a number that is not in this sequence but does belong in the closely related OEIS sequence A178805, which consists of $n$ that achieve record low values of $\| r(n) \|$ instead of $\log n \cdot \| r(n) \|$. In general a $\log n \cdot \| r(n) \|$ record is automatically also an $\| r(n) \|$ record, but the converse can fail on occasion. If we imagine that the $\| r(n) \|$ are independent random numbers uniformly distributed on $(0,1/2)$ then the probability that $\| r(n) \|$ is a new record is $1/n$, so we expect $\log N + O(1)$ record values with $n \leq N$. The same question for $\log n \cdot \| r(n) \|$ is trickier, but if I did this right the probability that $\| r(n) \|$ is a new record but $\log n \cdot \| r(n) \|$ is not one is approximately $1 / n \log n$, so we expect only $\log\log N + O(1)$ examples such as $n = 3040705645816$ up to $N$, and might never see another one even though there should be infinitely many more.

Here is a table of the values of $n < 2^{50}$ for which $\| r(n) \|$ attains a new record low, together with the signed fractional part of $r(n)$, and $\log n$ times that fractional part: $$ \begin{array}{rrrc} 2 & -0.1146099 & -0.0794415 & \\ 5 & 0.1066747 & 0.1716863 & ! \\ 9 & 0.0960765 & 0.2111017 & ! \\ 13 & 0.0683262 & 0.1752532 & ! \\ 17 & 0.0002541 & 0.0007199 & \\ 163 & -1.26 \cdot 10^{-6} & -6.43 \cdot 10^{-6} & \\ 53453 & 1.22 \cdot 10^{-6} & 1.33 \cdot 10^{-5} & ! \\ 110673 & 6.68 \cdot 10^{-7} & 7.76 \cdot 10^{-6} & ! \\ 715533 & 3.84 \cdot 10^{-7} & 5.17 \cdot 10^{-6} & \\ 1432276 & 2.33 \cdot 10^{-7} & 3.30 \cdot 10^{-6} & \\ 6517719 & -2.00 \cdot 10^{-7} & -3.14 \cdot 10^{-6} & \\ 11523158 & -9.95 \cdot 10^{-8} & -1.62 \cdot 10^{-6} & \\ 11985596 & -7.26 \cdot 10^{-8} & -1.18 \cdot 10^{-6} & \\ 24102781 & 4.43 \cdot 10^{-9} & 7.53 \cdot 10^{-8} & \\ 254977309 & 9.12 \cdot 10^{-10} & 1.76 \cdot 10^{-8} & \\ 451207448 & 3.68 \cdot 10^{-10} & 7.33 \cdot 10^{-9} & \\ 1219588338 & -2.57 \cdot 10^{-10} & -5.38 \cdot 10^{-9} & \\ 2048539023 & -5.89 \cdot 10^{-11} & -1.26 \cdot 10^{-9} & \\ 10066616717 & 4.85 \cdot 10^{-11} & 1.12 \cdot 10^{-9} & \\ 42116139191 & -4.47 \cdot 10^{-11} & -1.09 \cdot 10^{-9} & \\ 47657002570 & -2.43 \cdot 10^{-11} & -5.97 \cdot 10^{-10} & \\ 73831354169 & 1.35 \cdot 10^{-11} & 3.38 \cdot 10^{-10} & \\ 122478947521 & 7.53 \cdot 10^{-13} & 1.92 \cdot 10^{-11} & \\ 143949453227 & -5.50 \cdot 10^{-13} & -1.41 \cdot 10^{-11} & \\ 3040705645816 & 5.18 \cdot 10^{-13} & 1.49 \cdot 10^{-11} & ! \\ 3152420311977 & -3.36 \cdot 10^{-13} & -9.67 \cdot 10^{-12} & \\ 5624690531099 & 1.28 \cdot 10^{-13} & 3.76 \cdot 10^{-12} & \\ 14964977749017 & -7.15 \cdot 10^{-14} & -2.17 \cdot 10^{-12} & \\ 25999244327633 & -2.02 \cdot 10^{-14} & -6.25 \cdot 10^{-13} & \\ 92799025313425 & 6.01 \cdot 10^{-15} & 1.93 \cdot 10^{-13} & \\ 164330745650026 & -1.00 \cdot 10^{-15} & -3.28 \cdot 10^{-14} & \\ 604329910739082 & -4.59 \cdot 10^{-16} & -2.27 \cdot 10^{-14} & \end{array} $$ the "!"'s mark the $\| r(n) \|$ records that aren't $\log n \cdot \| r(n) \|$ records.

$\endgroup$
3
  • $\begingroup$ Got it. Your first three without exclamation marks are n = 2, 17, 163. So the log factor outside the || || does not usually matter, on account of being nearly constant I guess.. $\endgroup$
    – Will Jagy
    Dec 24, 2012 at 23:14
  • $\begingroup$ Noam, Thanks for providing this new life to the old question. $\endgroup$ Dec 25, 2012 at 3:28
  • $\begingroup$ Can you say anything about how many records there are in $||r(n)||$ that are not records in $\log n \dot ||r(n)||$? $\endgroup$
    – Zach H
    Dec 25, 2012 at 17:07
4
$\begingroup$

Hi Wadim, I decided to do a numerical run the same way that Kevin O'Bryant did for the previous question, but this time for the easiest version of my revised problem, find new record lows for $$ \parallel n / \log n \parallel \cdot \log n $$

       2      0.0794415
      17      0.000719936
     163      6.42582e-06
  715533      5.17294e-06
 1432276      3.30032e-06
 6517719      3.13803e-06
11523158      1.61843e-06
11985596      1.18403e-06
24102781      7.51947e-08

The results are pretty similar to what O'Bryant found. I suspect there is an infinite sequence of "champion" numbers. I do not think any full analysis of these is possible (you mention Lambert $W$), but there might (who knows?) be a subsequence with an explicit Ramanujan style recipe for construction.

Meanwhile, this is from C++ using "double" type, I imagine the accuracy is good enough. Easy enough to confirm with arbitrary precision in GP-Pari.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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