One inequality inspired by Erdős
Barbora Batíková, Tomáš J. Kepka and Petr C. Němec
Abstract
. One less common inequality in positive integers is carefully examined.
1991 Mathematics Subject Classification
11D75
In 1845, J. Bertrand (
[
1
]
, pg. 129) conjectured such a statement: ”For every integer
n
greater than 6 there always exists at least one prime number contained between
n-2
and
\frac{n}{2}
.” Bertrand himself noticed that his proposition (postulate) was true for all
n
such that
7\leq n<6\cdot 10^{6}
and believed it remained true for all
n\geq 7
. Seven years later, P. L. Tchebychef published a complete proof of the conjecture (
[
4
]
) and various simplifications of this proof appeared through passing years. It was P. Erdös in 1932 (
[
3
]
) who came up with an elegant and simple proof based on different ideas – prime decompositions of binomial coefficients (a thorough exposition of all this can be found in
[
2
]
). The approach of Erdös may be considered the standard one nowadays. Two remarks could turn out to be of some interest, however. Firstly, a formally weaker form of the postulate is shown in
[
3
]
. Namely, that for every positive integer
n
there is at least one prime
p
with
n
0
and
a
is the least integer with
2a\geq 3(r(b)+1)m(b)+4
then
x(n)>0
.
Proof.
(i) The sequences
z(n),m(n),r(n)
are non-decreasing.
(ii) Since
3z(b)<2b\leq 3(r(a)+1)m(a)
, we have
x(n)\leq z(b)-(r(a)+1)m(a)<0
by (i).
(iii) Since
3z(a)+3\geq 2a\geq 3(r(b)+1)m(b)+4
,
x(n)\geq z(a)-(r(b)+1)m(b)>0
by (i).
∎
Using this observation, we can expand negative values of
x(n)
up and positive values down.
In order to facilitate the calculation of
x(n)
, it is useful to distinguish intervals where the values of
m(n)
and
r(n)
are constant (and thus the values of
x(n)
are non-decreasing).
Lemma 2
.
Let
a
be a positive integer with
r(a)=s
and
m(a)=t
,
q
be the largest integer such that
2q<(t+1)^{2}
and
b(a)=\min(q,2^{s})
. Then
b(a)
is the largest positive integer
k
such that
r(k)=s
,
m(k)=t
and if
n_{1},n_{2}
are positive integers such that
a\leq n_{1}\leq n_{2}\leq b(a)
then
x(a)\leq x(n_{1})=z(n_{1})-(r(a)+1)m(a)\leq x(n_{2})\leq x(b(a))
.
Proof.
If
n>b(a)
then either
n>2^{s}
and
r(n)\geq s+1
, or
n>q
, hence
2n\geq(t+1)^{2}
and
m(n)\geq t+1
. The rest follows from the fact that the sequence
z(n)
is non-decreasing.∎
Remark 1
.
If
s=2k
is even then
(2^{k})^{2}=2^{2k}<2\cdot 2^{2k}=2^{2k+1}<2^{2k+2}=(2k+1)^{2}
, and hence
2^{k}\leq m(2^{s})<2^{k+1}
. Further, by obvious induction, there is
p
such that
2^{2k+1}=3p+2
. As
2^{2k+1}=2\cdot 2^{k}
,
z(2^{s})=p
.
If
s=2k+1
is odd then
(2^{k+1})^{2}=2\cdot 2^{2k+1}
,
m(2^{s})=2^{k+1}
, there is
q
such that
2^{2k+2}=3q+1
and
z(2^{s})=q
.
Now, let
n
be such that
2^{s}0
whenever
k\geq 6
. If
k\geq 6
and
s=2k+1
then
m(2^{s+1})<2^{k+2}
and
3x(n)>2^{2k+2}-1-3(s+2)2^{k+2}=2^{k+2}(2^{k}-6k-9)-1\geq 2^{k+2}-1>0
.
We have proved that
x(n)>0
for every
n>2^{12}=4096
(
=4^{6}\cdot 9^{0}
). Further,
z(4096)=2730
,
m(4096)=90
,
r(4096)=12
and
x(4096)=1560
.
Theorem 1
.
Let
n
be a positive integer.
(i)
x(n)=0
if and only if
n\in\{436,451,529,545,546\}
.
(ii)
x(n)<0
if and only if either
n\leq 435
or
n=450
or
513\leq n\leq 528
.
(iii)
x(n)>0
if and only if either
437\leq n\leq 512
,
n\neq 450,451
or
n\geq 530
,
n\neq 545,546
.
(iv)
x(n)>0
for every
n\geq 547
.
(v)
x(n)
has no maximal value.
(vi)
x(129)=-59
and
x(n)\geq-58
for
n\neq 129
.
Proof.
(i) – (iv). Taking into account Remark
1
, we may assume that
n\leq 4095
. From the table in Exercise
1
, it is clear that
x(n)<0
for
1\leq n\leq 13
. As
r(13)=4
and
m(13)=5
, by Lemma
1
(ii) for
a=13
we obtain
b=37
. As
x(38)=-31
,
r(38)=6
and
m(38)=8
, Lemma
1
(ii) for
a=38
yields
b=84
.
Using repeatedly Lemma
1
(ii) for
a=85,157,230,284,346,391,406,421
, we see that
x(n)<0
for
1\leq n\leq 435
and
x(436)=0
.
As
x(4095)=1559
,
r(4095)=12
and
m(4095)=90
, Lemma
1
(iii) for
b=4095
gives
a=1757
. Further,
x(1756)=462
,
r(1756)=11
and
m(1756)=59
. By Lemma
1
(iii) for
b=1756
we have
a=1064
.
Using repeatedly Lemma
1
(iii) for
b=1063,829,661,596,562
, we see that
x(n)>0
for
4095\geq n\geq 547
and
x(546)=0
.
Now it remains to determine the sign of
x(n)
for
436\leq n\leq 546
. We will use Lemma
2
.
As
r(436)=9
and
m(436)=29
,
b(436)=449
. However
x(437)=1
, and hence
x(n)>0
for
437\leq n\leq 449
. Further,
r(450)=9
,
m(450)=30
and
b(450)=480
. As
x(450)=-1
,
x(451)=0
and
x(452)=1
,
x(n)>0
for
452\leq n\leq 480
.
Continuing in this way,
x(481)=10
,
r(481)=9
and
m(481)=31
. Then
b(481)=511
and
x(512)=21
. Thus
x(n)>0
for
481\leq n\leq 512
. Further,
r(513)=10
,
m(513)=32
and
b(513)=544
. If
513\leq n\leq 544
then
x(n)=z(n)-352
. As the number 352 is even, there is exactly one
n
with
z(n)=352
, namely
n=529
. Finally,
x(545)=0
.
(v) Indeed, taking into account Remark
1
, if
B
is an arbitrary positive integer and
k
is such that
2^{k+2}>3B+1
then
x(2^{2k+2})>B
.
(vi) Using Lemma
2
, for every
i=1,2,\dots
we define the number
k_{i}
by
k_{1}=1
and
k_{i+1}=b(k_{i})+1
. Then, for every positive integer
i
,
r(k_{i})=r(k_{i+1}-1)
,
m(k_{i})=m(k_{i+1}-1)
,
r(k_{i+1})=r(k_{i})+1
or
m(k_{i+1})=m(k_{i})+1
and if
k_{i}\leq n_{1}\leq n_{2}\leq k_{i+1}-1
then
x(n_{1})=z(n_{1})-(r(k_{i})+1)m(k_{i})\leq x(n_{2})
. Thus
k_{i}\leq n\leq k_{i+1}-1
,
i=1,2,\dots
, are maximal intervals where
r(n),m(n)
are constant.
The first 37 intervals
k_{i}\leq n\leq k_{i+1}-1
are presented in the following table (the calculations, although a bit tedious, are extremely easy):
(1)
If
n=1
then
r(n)=0
,
m(n)=1
,
x(n)=-1
.
(2)
If
n=2
then
r(n)=1
,
m(n)=2
,
x(n)=-3
.
(3)
If
3\leq n\leq 4
then
r(n)=2
,
m(n)=2
,
-5\leq x(n)\leq-4
.
(4)
If
5\leq n\leq 7
then
r(n)=3
,
m(n)=3
,
-9\leq x(n)\leq-8
.
(5)
If
n=8
then
r(n)=3
,
m(n)=4
,
x(n)=-11
.
(6)
If
9\leq n\leq 12
then
r(n)=4
,
m(n)=4
,
-15\leq x(n)\leq-13
.
(7)
If
13\leq n\leq 16
then
r(n)=4
,
m(n)=5
,
-17\leq x(n)\leq-15
.
(8)
If
n=17
then
r(n)=5
,
m(n)=5
,
x(n)=-19
.
(9)
If
18\leq n\leq 24
then
r(n)=5
,
m(n)=6
,
-25\leq x(n)\leq-21
.
(10)
If
25\leq n\leq 31
then
r(n)=5
,
m(n)=7
,
-26\leq x(n)\leq-22
.
(11)
If
n=32
then
r(n)=5
,
m(n)=8
,
x(n)=-27
.
(12)
If
33\leq n\leq 40
then
r(n)=6
,
m(n)=8
,
-35\leq x(n)\leq-30
.
(13)
If
41\leq n\leq 49
then
r(n)=6
,
m(n)=9
,
-36\leq x(n)\leq-31
(14)
If
50\leq n\leq 60
then
r(n)=6
,
m(n)=10
,
-37\leq x(n)\leq-31
.
(15)
If
61\leq n\leq 64
then
r(n)=6
,
m(n)=11
,
-37\leq x(n)\leq-35
.
(16)
If
65\leq n\leq 71
then
r(n)=7
,
m(n)=11
,
-45\leq x(n)\leq-41
.
(17)
If
72\leq n\leq 84
then
r(n)=7
,
m(n)=12
,
-49\leq x(n)\leq-41
.
(18)
If
85\leq n\leq 97
then
r(n)=7
,
m(n)=13
,
-48\leq x(n)\leq-40
.
(19)
If
98\leq n\leq 112
then
r(n)=7
,
m(n)=14
,
-47\leq x(n)\leq-38
.
(20)
If
113\leq n\leq 127
then
r(n)=7
,
m(n)=15
,
-45\leq x(n)\leq-36
.
(21)
If
n=128
then
r(n)=7
,
m(n)=16
,
x(n)=-43
.
(22)
If
129\leq n\leq 144
then
r(n)=8
,
m(n)=16
,
-59\leq x(n)\leq-49
(23)
If
145\leq n\leq 161
then
r(n)=8
,
m(n)=17
,
-57\leq x(n)\leq-46
.
(24)
If
162\leq n\leq 180
then
r(n)=8
,
m(n)=18
,
-55\leq x(n)\leq-43
.
(25)
If
181\leq n\leq 199
then
r(n)=8
,
m(n)=19
,
-51\leq x(n)\leq-39
.
(26)
If
200\leq n\leq 220
then
r(n)=8
,
m(n)=20
,
-47\leq x(n)\leq-34
.
(27)
If
221\leq n\leq 241
then
r(n)=8
,
m(n)=21
,
-42\leq x(n)\leq-29
.
(28)
If
242\leq n\leq 256
then
r(n)=8
,
m(n)=22
,
-37\leq x(n)\leq-28
.
(29)
If
257\leq n\leq 264
then
r(n)=9
,
m(n)=22
,
-49\leq x(n)\leq-45
.
(30)
If
265\leq n\leq 287
then
r(n)=9
,
m(n)=23
,
-54\leq x(n)\leq-39
.
(31)
If
288\leq n\leq 312
then
r(n)=9
,
m(n)=24
,
-49\leq x(n)\leq-33
.
(32)
If
313\leq n\leq 337
then
r(n)=9
,
m(n)=25
,
-42\leq x(n)\leq-26
.
(33)
If
338\leq n\leq 364
then
r(n)=9
,
m(n)=26
,
-35\leq x(n)\leq-18
.
(34)
If
365\leq n\leq 391
then
r(n)=9
,
m(n)=27
,
-27\leq x(n)\leq-10
.
(35)
If
392\leq n\leq 420
then
r(n)=9
,
m(n)=28
,
-19\leq x(n)\leq-1
.
(36)
If
421\leq n\leq 449
then
r(n)=9
,
m(n)=29
,
-10\leq x(n)\leq 9
.
(37)
If
450\leq n\leq 480
then
r(n)=9
,
m(n)=30
,
-1\leq x(n)\leq 19
.
From the preceding table it is clear that
x(n)\geq-59
for
1\leq n\leq 450
and
x(129)=-59
. However
x(513)=-11
and
b(513)=544
, and hence (ii) implies that
x(n)\geq-11
whenever
n\geq 451
. As
129=k_{22}
and
x(130)=-58
,
x(n)\geq-58
for
n\neq 129
. ∎
Remark 2
.
Thus 547 is the least positive integer
n
such that
x(m)>0
for each
m\geq n
. Notice that 547 is the onehundred-first prime number and that 101 is a prime as well. Besides,
1+0+1=2
,
16=2^{4}=5+4+7
,
7=1+6
.