Very challenging: max{floor,ceil}=?

Question

I spotted a pattern while trying to generalize a problem. (EDIT: said problem has been removed from this post to avoid confusion. EDIT(2): Here is the problem again: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=367432&sid=356f2a2b519ab007bb648bf00e84934d#p367432 ) <--- That isnt the problem I want to solve, it is just where I got the pattern below from. I know how to solve the problem in the link already; I am only here trying to solve the problem below:

Here is the pattern I found, which I cannot prove. If you prove this, you win the bounty, and if there are multiple proofs, the most detailed (including extra information, etc) wins:

If $$\{k:k\in \mathbb{Z}^+,k\ne 4, k\ge 3\}$$,

$$\max\left\{\left(\frac{k}{\lfloor \frac{k}{\text{e}}\rfloor }\right)^{\lfloor \frac{k}{{\text{e}}}\rfloor},\left(\frac{k}{\lceil \frac{k}{\text{e}}\rceil }\right)^{\lceil \frac{k}{{\text{e}}}\rceil}\right\}=\begin{cases}\left(\frac{k}{\lfloor \frac{k}{\text{e}}\rfloor }\right)^{\lfloor \frac{k}{{\text{e}}}\rfloor}\quad\text{if}\ \{\frac{k}{\text{e}}\}<0.5\\ \\\left(\frac{k}{\lceil \frac{k}{\text{e}}\rceil }\right)^{\lceil \frac{k}{{\text{e}}}\rceil}\quad\text{if}\ \{\frac{k}{\text{e}}\}\ge 0.5\end{cases}$$.

I honestly don't know where to begin.

EDIT: Here $\{x\}$ denotes the fractional part of $x$, e.g. $\{5.4\}=0.4$.

Answer 1

Your conjecture is correct for $k$ sufficiently large and, almost surely, the only counterexample is the case $k=4$ you have already noted. This inequality is insanely tight: In the end, it comes down to the fact that $e/6 < 1/2$ and some very fortunate coincidences concerning the continued fraction of $e$.

We put $n = \lfloor k/e \rfloor$. We have $$\left( \frac{k}{n} \right)^n < \left( \frac{k}{n+1} \right)^{n+1}$$ if and only if $$(n+1)^{n+1}/n^n < k.$$ We'll set $c=(n+1)^{n+1}/n^n$.

On the other hand, $\{ k/e \} > 1/2$ is equivalent to $k/e>n+1/2$, or $k>e(n+1/2)$. So your conjecture is $$k> c \Longleftrightarrow k > e(n+1/2).$$ In other words, if you had a counterexample to your conjecture, there would be an integer $k$ between $c$ and $e(n+1/2)$. We'll rule this out.

To this end, I need to replace $c$ by something more convenient. I claim that $e(n+1/2) > c>e (n+1/2-1/(23.9 (n+1/2)))$ for $n \geq 4$. This is definitely true for $n$ sufficiently large, as $$c = n \exp\left((n+1) \log\left(1+\frac{1}{n}\right)\right) = n \exp\left((n+1) \left(\frac 1 n -\frac{1}{2n^2} + \frac{1}{3 n^3}+O\left(\frac{1}{n^4}\right)\right)\right)$$ $$= e(n+1/2-1/(24 n) + O(1/n^2))$$ I also checked it for $4 \leq n \leq 100$. I haven't done the careful work of figuring out the constant in the $O()$ to prove this for all $n$, but you could if you needed to and, if I am wrong, it only introduces finitely many errors. (Here and in the following, you should think of numbers like $23.9$ as "essentially $24$", but I have put in a little fudge to make the inequalities true inequalities rather than asymptotics.)

Our goal is to show that there are no solutions to $$e(n+1/2-1/(23.9 (n+1/2))) < k < e(n+1/2)$$ in integers, except for $k=4$ and $n=1$ (as already noted). We can already see that, if there are any solutions, they are rare: you need to get an interval of length $1/(24 n)$ to contain an integer. We will actually see that there aren't any.

Applying $x \mapsto e-x/(n+1/2)$ to each term, this equation is equivalent to: $$\frac{e}{23.9 (n+1/2)^2} > e-\frac{2k}{2n+1} > 0$$ or $$\frac{e}{5.975 (2n+1)^2} > e-\frac{2k}{2n+1} > 0 \quad (\ast).$$

We now remember a theorem about continued fractions (see, for example, Theorem 184 in Hardy and Wright): If $x$ is irrational and $p$ and $q$ are integers with $$\left| x - \frac{p}{q} \right| < \frac{1}{2 q^2}$$ then $p/q$ is a convergent of $x$. Since $e/5.975 < 1/2$, if we had a solution to $(\ast)$, then $(2k)/(2n+1)$ would be a convergent of $e$. (Since convergents grow exponentially fast, this already proves that solutions to $(\ast)$ are very rare.) Roughly, the rest of the proof is as follows: If you look at the convergents $p_i/q_i$ of $e$ and compute $q_i^2 |e-p_i/q_i|$ you'll see that it is approaching $1/2$ for $i \equiv 1, 3 \bmod 3$ and going to zero for $i \equiv 2 \bmod 3$. Since $1/2 > e/5.975$, we don't expect any solutions in the first case. In the second case, it happens that $p_i/q_i$ is of the form $\mbox{odd}/\mbox{odd}$, not $(2k)/(2n+1)$. The rest of the argument is filling in the details of this.

We recall the basic formulas of the theory of continued fractions: If $x = a_0+1/(a_1+1/(a_2+1/(a_3 + \cdots))) =: [a_0, a_1, a_2, a_3, \cdots]$ and the convergents of $x$ are $p_1/q_1$, $p_2/q_2$, etcetera, than $p_{i+1} = a_i p_i +p_{i-1}$ and $q_{i+1} = a_i q_i + q_{i-1}$.

The continued fraction of $e$ is known: $$e = [2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,\cdots].$$ From now on, $a_i$ will denote the sequence $2$, $1$, $2$, $1$, $1$, $4$, etcetera and $p_i/q_i$ will denote the convergents, starting $p_1/q_1=2/1$, $p_2/q_2 = 3/1$, $p_3/q_3=8/3$, $p_4/q_4 = 11/4$, etcetera. (Note that $8/3$ corresponds to $k=4$, $n=1$.)

From the relations $p_{i+1} = a_i p_i +p_{i-1}$ and $q_{i+1} = a_i q_i + q_{i-1}$, we check that the parity of $(p_i, q_i)$ repeats with period $6$. The terms of the form $(2k)/(2n+1)$ are appear in positions that are $1$ or $3$ modulo $6$, starting $$2, \ 8/3,\ 106/39,\ 1264/465,\ 25946/9545,\ 517656/190435, \cdots$$ I checked the $4$ convergents after $8/3$ explicitly and they did not violate $(\ast)$, so I can assume that I am dealing with some quite large numbers if there are any counterexamples.

We have the alternating sum $\left| e-p_i/q_i \right| = 1/(q_i q_{i+1}) - 1/(q_{i+1} q_{i+2})+ \cdots$ and thus, in particular, $\left| e-p_i/q_i \right| > 1/(q_i q_{i+1}) - 1/(q_{i+1} q_{i+2})$. In the cases we care about, $e>p_i/q_i$ so we can drop the absolute value.

Case 1: $i=1 \bmod 6$, like $106/39$. Note that the denominators surrounding $39$ are $7$, $32$, $39$, $71$, $495$. $$\frac{1}{q_i q_{i+1}} - \frac{1}{q_{i+1} q_{i+2}} = \frac{1}{q_i (2 q_{i} - q_{i-2})} - \frac{1}{q_{i+1} q_{i+2}}.$$ But $q_{i-2}/q_i$ and $q_i/q_{i+2} \to 0$ as $i \to \infty$ while $1 \bmod 6$ (these are $7/39$ and $39/495$ in the example), so $$q_i^2 \left( \frac{1}{q_i (2 q_{i} - q_{i-2})} - \frac{1} {q_{i+1} q_{i+2}} \right) \to 1/2.$$ Already $i=13$ gets you past $e/5.975$, so there are no solutions in this case.

Case 2: $i \equiv 3 \bmod 6$, like $1264/465$. Note that the denominators surrounding $465$ are $71$, $465$, $536$, $1001$. In this case, we have $$\frac{1}{q_i q_{i+1}} - \frac{1}{q_{i+1} q_{i+2}} =\frac{1}{q_i q_{i+1}} - \frac{1}{q_{i+1}(q_i+ q_{i+1})} = \frac{1}{q_i (q_i+q_{i+1})} = \frac{1}{q_i (2 q_i + q_{i-1})}.$$ Again, $q_{i-1}/q_{i} \to 0$ (this is $71/465$ in the example) so $$q_i^2 \frac{1}{q_i (2 q_i + q_{i-1})} \to 1/2.$$ Taking $i=9$ already gets you past $e/5.975$.

Answer 2

Not an answer, just an observation - hence CW.

The plot of

$\text{max} \begin{cases} \dfrac{e}{k}\log\left(\dfrac{k}{\lfloor k/e\rfloor}^{\lfloor k/e\rfloor}\right)\\ \\ \dfrac{e}{k}\log\left(\dfrac{k}{\lceil k/e\rceil}^{\lceil k/e\rceil}\right)\\ \end{cases}$

against background $\mod \dfrac{e}{2}$

shows that what you conjecture is not strictly true, but it certainly approaches that limit (if I have understood the problem correctly).

Update

For $e\pm\frac{1}{2}$, fractional part $\pm\frac{1}{4}$:

Manipulate[s = E + m; pr2 = 1.005; pr1 = 0.94; r1 = s; c = m/E;Show[Plot[{If[FractionalPart[k/s] < 0.5 - m/2, 1.1, 0], 1}, {k, r1, (r1 + 5 s)}, PlotStyle -> {{Opacity[0]}, {Opacity[0]}},Filling -> {1 -> {2}}, FillingStyle -> {Opacity[0.2]},Frame -> True, Axes -> False, GridLines -> {{}, {1}},GridLinesStyle -> {Gray, Dashing[0.01]},PlotRange -> {{r1, (r1 + 5 s)}, {pr1, pr2}}], Plot[{If[Log[(k/Floor[k/s])^Floor[k/s]]/(k/s) - c >Log[(k/Ceiling[k/s])^Ceiling[k/s]]/(k/s) - c,Log[(k/Floor[k/s])^Floor[k/s]]/(k/s) - c, I],If[Log[(k/Ceiling[k/s])^Ceiling[k/s]]/(k/s) - c >Log[(k/Floor[k/s])^Floor[k/s]]/(k/s) - c,Log[(k/Ceiling[k/s])^Ceiling[k/s]]/(k/s) - c, I]}, {k,r1, (r1 + 5 s)}, PlotStyle -> {{Red, Thick}, {Blue, Thick}}, Frame -> True,Axes -> False, PlotRange -> {{r1, (r1 + 5 s)}, {pr1, pr2}}]], {{m, 0}, -0.5, 0.5}]

Answer 3

Not an answer, but an approach: Fix a $k$ and let $K := \lceil \frac{k}{e} \rceil$. Suppose $\left\{ \frac{k}{e} \right\} \ge \frac12$. We want to show that \begin{align*} \left(\frac{k}{\lfloor \frac ke \rfloor}\right)^{\lfloor \frac ke \rfloor} \le \left(\frac{k}{\lceil \frac ke \rceil}\right)^{\lceil \frac ke \rceil} \end{align*} Basic transformations (and the fact that $K = \lceil \frac ke \rceil = \lfloor \frac ke \rfloor + 1$) yield the equivalent inequality \begin{align*} K^K \le k \cdot (K - 1)^{K - 1} \end{align*} Now our assumption $\left\{ \frac{k}{e} \right\} \ge \frac12$ means $\frac ke \ge \lfloor \frac ke \rfloor + \frac 12 = K - \frac 12$. Hence \begin{align*} k \cdot (K - 1)^{K - 1} \ge e \cdot \left(K - \frac12\right) \cdot (K - 1)^{K - 1} \end{align*} Plugging this in above and transforming, we see that it is sufficient to show that \begin{align*} \left(\frac{K}{K-1}\right)^K \le e \cdot \frac{K - \frac12}{K - 1} \end{align*} Taking the reciprocal and multiplying by $e$, we get the equivalent inequality \begin{align*} \left(1 - \frac1K\right)^K \cdot e \ge \frac{K - 2}{K - 1} \end{align*} Both sides converge to $1$ as $K \to \infty$ (here the role of the constant $e$ becomes apparent).

If we want to prove the other case, i. e., $\left\{ \frac ke \right\} < \frac12$, we analogously arrive at \begin{align*} \left(1 - \frac1K\right)^K \cdot e < \frac{K - 2}{K - 1} \end{align*}

I could not proceed from here since I don't know enough about the convergence of $(1+\frac xn)^n$. I am not even sure whether this helps at all, but I wanted to post it since it explains where the $e$ comes from.