3^n - 2^n and relatives

5 views
Skip to first unread message

Gottfried Helms

unread,
May 21, 2004, 9:30:01 AM5/21/04
to
Hi -

I got an unequality, which i'm unable to analytically to disprove.
Does anyone know useful related material?

The inequality, formulating a restriction, arose whily studying
the question of a certain, primitive assumed loop in the collatz
(3x+1)-problem. Here it goes:

3^L - 1
powceil2( 3^L ) <= 2^L* -------
2^L - 1

where powceil2 ( x) = smallest power 2^S >= x

Empirically the lhs is always *greater* than the rhs (up to L=200)
(Thanks to Otto Forster, Uni Muenchen for his GPL-Freeware num-theory
interpreter-program ARIBAS!)

The benefit of this inequality is, that if it cannot be satisfied,
then a primitive loop in the Collatz-problem cannot exist.


One can reformulate this formulafor instance to:


3^L 3^L - 1
powceil2( ---- ) <= ----------
2^L 2^L - 1

- or many other ways... I didn't find a definitve form, where I could
directly conclude the impossibility of that inequality.

Someone with an idea?

Regards -

Gottfried Helms

Gareth McCaughan

unread,
May 23, 2004, 7:00:01 PM5/23/04
to
Gottfried Helms <he...@uni-kassel.de> writes:

> I got an unequality, which i'm unable to analytically to disprove.
> Does anyone know useful related material?
>
> The inequality, formulating a restriction, arose whily studying
> the question of a certain, primitive assumed loop in the collatz
> (3x+1)-problem. Here it goes:
>
> 3^L - 1
> powceil2( 3^L ) <= 2^L* -------
> 2^L - 1
>
> where powceil2 ( x) = smallest power 2^S >= x

According to theorems mentioned at the start of chapter 3
of Baker's "Transcendental Number Theory", the following is
true.

Let A1, ..., An >= 4 and B >= 2, and suppose that ...
a1,...,an are algebraic numbers with height(ak) <= Ak
b1,...,bn are rational integers with |bk| <= B.
Write F := b1 log a1 + ... + bn log an. Then either
F=0 or |F| > B^-(C Q log Q), where Q = product(log Ak) and
C depends only on n and on d, the maximum degree of the ak.

In particular, let n=2 and d=1; let a1=2, a2=3; and
write p = b1, q = -b2. Then this says
F = |p log 2 - q log 3|
either F = 0 or |F| > max(p,q)^-C
for a constant C.

C can be found explicitly. Baker's book doesn't give
details of how, but they are out there in the literature.
There have been advances in this area since Baker's book.
(Search Google for "laurent mignotte nesterenko".)
The value of C will still be much larger than you'd
like :-).

Anyway: if the inequality above (the one you want to prove
can't happen) holds then you can find p,q with |F| <= 2^-p
or something like that. And if F is small then p and q
have to be somewhat similar in size.

Now, if p^-C < F <= 2^-p then -C log p <= -p log 2, so
p / log p <= C / log 2. So you can get an upper bound on
the size of p. It may or may not be practical then to
check all actual values of p up to there.

A nasty back-of-envelope calculation using a version
of Laurent-Mignotte-Nestorenko quoted in a paper I've
found on the web suggests that actually you get some
such bound as
|F| >= exp(-17280) / p^(8640+1080 log p)
where those numbers could doubtless be reduced by being
less sloppy than I was, but probably not hugely reduced.
So, that would lead to a contradiction when
2^-p p^(8640+1080 log p) < exp(-17280)
-p + 8640 log p + 1080 (log p)^2 < -17280
p - 8640 log p - 1080 (log p)^2 > 17280
which is true provided p >= 298000 or thereabouts.

So ... if I haven't botched the above in any way (which
I probably have), you "only" need to check a few hundred
thousand values of L. You'd do that in practice by calculating
log 3 / log 2 with sufficient accuracy (plain ol' double
precision should be fine) and looking to see how close to
an integer you can get by multiplying it by an integer
up to a few hundred thousand in size.

--
Gareth McCaughan
.sig under construc

Gareth McCaughan

unread,
May 24, 2004, 7:30:14 PM5/24/04
to
I wrote:

> According to theorems mentioned at the start of chapter 3
> of Baker's "Transcendental Number Theory", the following is
> true.

..


> So ... if I haven't botched the above in any way (which
> I probably have), you "only" need to check a few hundred
> thousand values of L. You'd do that in practice by calculating
> log 3 / log 2 with sufficient accuracy (plain ol' double
> precision should be fine) and looking to see how close to
> an integer you can get by multiplying it by an integer
> up to a few hundred thousand in size.

I just received some e-mail from a friend of mine who knows
much more about number theory than I do, observing that
(1) it's rather well known (to those who know such things,
I suppose) that the 3n+1 conjecture itself follows from
some sort of bounds on the approximability of log 3 / log 2
by rationals, and (2) that the required bounds are much
tighter than those obtainable by methods of the sort I
mentioned. So if Gottfried Helms's conjecture is strong
enough to do much for the 3n+1 conjecture (I'm not sure
what a "primitive loop" is, I'm afraid) then the argument
I sketched probably has some big holes in it. Contrariwise,
if I've somehow managed to break my perfect record of
never posting anything to sci.math.research without at
least one serious mistake, then Gottfried's conjecture
probably doesn't imply anything very exciting about the
Collatz conjecture. It's after midnight local time and
I should be in bed, so I shan't attempt to determine
which of the three possibilities -- the third being
that Gottfried and I are both right, and that Gottfried
has found a way to make progress on Collatz with weaker
inequalities than others have obtained -- is the truth.
I'm just sounding a note of caution. :-)

--
Gareth McCaughan
sig under construc

Gottfried Helms

unread,
May 25, 2004, 12:26:36 PM5/25/04
to
Gareth McCaughan schrieb::

>
> According to theorems mentioned at the start of chapter 3
> of Baker's "Transcendental Number Theory", the following is
> true.

(...)

Hi Gareth -

that's an very interesting material, thank you (hope, I'll
ever learn to apply that myself). I'll study it in more detail
next days, since I'm guessing another connection to that field
here, where my derivations on number-structure possibly could
give additional information - or at least some more insight
- I'll post it another day.

For an explanation for the origin of my question please see my
other post.


Regards -

Gottfried Helms

Gottfried Helms

unread,
May 25, 2004, 12:17:31 PM5/25/04
to
Gareth McCaughan schrieb::

Hmmm, the stated inequality results from a "primitive" loop,
let me explain that.

---------------------


Assume the transformation T on an odd x with the parameter A

y= T(x;A)

being

y= (3x+1)/2^A

where A is the highest exponent keeping y integral (which is
actually only a short form for multiple steps of the collatz-
transformation, collecting all subsequent x/2 - operations)
and allowing short form for recursive notation:

z= T(y;B) = T(T(x;A);B) = T(x;A,B)

then a loop of, for instance, length 2 occurs, if

z = T(x;A,B) = x


------------------------------------------


The occuring equations are under investigation in some articles,
that I've come across (mostly via internet), and are obviously
difficult to handle, but of high general interest, as I learned
this way.

My first approach was to deal with any type of loop, the general
form

x = T(x;A,B,C,D,..M)
= T(x;A,B,C,D,...,M,A,B,C,...M)
= T(x;A,B,C...)...

for what I've got some nice results, but still not in the form of a
general formulation, which could, for instance, easily been transferred
to 5x+1 and other classes of the problem.

So I decided, first to investigate a somehow "primitive" loop.

I assumed most primitive loop (besides the trivial one, which is in this
notation 1 = T(1;2) = T(1;2,2) = T(1;2,2,2,2,2,2,...) ) for my
purposes the type of loop, which starts with one or more ascending steps,
and then descends in one step.

These are the assumed loops of the form

x = T(x;1,1,1,1,...,1,A)

where immediately strong restrictions apply on A.

One reason why I assumed that type as somehow primitive, is, that any
eventual loop can be expressed as a collection of ascending steps between
descending steps, if the length 0 is allowed.

So an arbitrary transformation, for instance

y = T(x;1,1,3,1,4,2,1,1,3)

can be segmented in

y = T( T(T(T(T(x;1,1,3);1,4);2);1,1,3)

and eventually I can use my tools, that I developed in the analysis of
the "primitive" loop.


-------------------------------------------------------------


If I analyse the transformation of length N

z = T(x;1,1,1,1,...,1,A) where the number of ones is denoted as "L",

and check, whether it is ever possible, that we find a solution in integers,
where z equals x, I come to an expression of the right hand side of
my inequality, that I stated her in my previous postings, which also
reflects an *additional* restriction.


With an arbitray 3-step-transformation, x' = T(x;A,B,C) with the length N=3,
where x' should equal x (thus realizing a loop)
with x,y,z, the intermediate values of each transformation,

we can formulate a strong restriction on the exponents A,B,C:

since y = (3x+1)/2^A z = (3y+1)/2^B x'=(3z+1)/2^C and x=x' assumed,

we can write their product as

(3x+1) (3y+1) (3z+1)
xyz = ---------------------
2^(A+B+C)

Rearranging this we have:

(3x+1) (3y+1) (3z+1) 1 1 1
2^(A+B+C) = --------------------- = ( 3 + ---) ( 3 + ---) ( 3 + ---)
x * y * z x y z

and obviously the range for the rhs is 3^3 .. 4^3 , so the sum of the
exponents S=A+B+C must be an integer, which makes 2^S falling in between
this range.

3^N < 2^S <= 4^N (this is valid for any length N of assumed loop)
(for generalizations like the 5x+1-problem this
is equivalently 5^N < 2^S < 6^N)

Even more, this equation shows without any lengthy proof, that whenever the
sum S is in general 2*N, then *all* parentheses on the rhs must take their maximum,
and this is 4 for each of them.

This restricts then all x,y,z to be 1 , which in turn restricts all A,B,C to be 2.

Result: if S = 2*N then x = T(x;A,B,C,D...) only if A=B=C=D=...=2 and x = 1

----------------

It also shows a widely unknown property of the loop-problem, that the values
of x,y,z have *high bounds* - which is important, since often articles about
the collatz-problem assume loops in "high number" areas, if they don't find a
solution in small accessible values. That is definitely not true: the values
of the members of an eventual loop are much restricted in values.


Since the trivial loop is not of interest, we only have to study the cases

2^S < 4^N

and since 2^S must be at least the next power of 2 after 3^N we have the
inequality


powerceil2(3^N) <= 2^S < 4^N

Now from the expansion of the three transformations into explicit formulas
we get possible S; and I observed, that they were *always* smaller than
powerceil2(3^N) in my cases of primitive loops. The contributions here in
sci.math.research , sci.math and by some private posts showed, that there
is an *extremely* high likelihood, that this inequality never holds.
However - that's still no proof, even not for this simple case.

----------------------------------------------------------

I think, I made the needed progress now by investigating some modular
classes, which exhibited a useful, very simple structure for candidate
numbers x and y.

The above form of the inequality, stated for a "primitive" loop of length
N with L=N-1 ones and one exponent >1

x = T(x;1,1,1,1,1....1,C) with L ones, C>1 and x odd integer>1

This problem can be separated into two:

y = T(x;1,1,1,1,1,1...1) with L=N-1 ones ("iterated transformation")
z = T(y;C) where z should equal x

An iterated transformation like y=T(x;1,1,1,1,1....1) with L ones
restricts x and y to a very specific modular structure.

it comes out, that - with a free parameter i ranging of nonnegative
odd integers - x and y *must* have a very simple structure depending on
the length of the requested iterated transformation:

x = i * 2 * 2^L -1
y = i * 2 * 3^L -1

thus

3* ( i * 2 * 3^L -1 ) +1
z = (3y+1)/2^C = -------------------------
2^C

and if z = x

3* ( i*2*3^L -1 ) +1
x = i*2*2^L -1 = ----------------------
2^C

After rearranging I come to the equation

i*3^N -1
2^C = 2 * -------------
i*2^N -1

and with S = C + 1*L the stated inequality must hold:

i*3^N -1
powerceil(3^N) <= 2^S = 2^(C+L) = 2^L * 2 * --------- < 4^N
i*2^N -1


If this inequality does not hold, then such a type of loop
cannot exist - irrespectively of any assumend length.

-------------------------------------------------------

I stated this inequality for the case i=1 . For growing i the
middle part of the inequality is better written like the following

3^N - 1/i
2^N * ---------
2^N - 1/i

and this converges to 3^N, which is definitevely smaller than the
lhs:

for i->oo the inequality

powerceil2(3^N) <= 3^N

is obviously false.

So the case with i=1 was the most critical case, and I accept
the information and learned the arguments for the extremely
likelihood, that this inequality cannnot be satisfied for any
parameter L and C - but which is still not *proven*....

------------------------------------------------------------------

If that's solved, then at least a "primitive" loop can be actually
negated - which is surely no great step in the whole loop-problem or even
the general collatz problem - but... it's a start.
Therefore I'm also more interested in extensible proofs than in
min/max-estimations for separate cases, if they cannot be generalized to
other collatz-type-problems.

Unfortunately, a disproof of this type of collatz-loops is not conversely
saying something on the above inequality, insofar it concerns unproved
assumtions about the 2-log of 3 and the like, what you and others had
derived here - that's bad luck.

But I've got the impression, that some of my equations in this context
could be helpful for progress even in that regard.
I'll post them, if I've time these days.

Hope I answered the questions, that you rose in your post, even if
I had difficulties to really follow your four segments today... :-)


Regards -

Gottfried Helms


Gottfried Helms

unread,
May 27, 2004, 8:26:37 AM5/27/04
to
Am 24.05.04 01:00 schrieb Gareth McCaughan:

> Gottfried Helms <he...@uni-kassel.de> writes:
>
>
>> I got an unequality, which i'm unable to analytically to disprove.
>> Does anyone know useful related material?
>>
>> The inequality, formulating a restriction, arose whily studying
>> the question of a certain, primitive assumed loop in the collatz
>> (3x+1)-problem. Here it goes:
>>
>> 3^L - 1
>> powceil2( 3^L ) <= 2^L* -------
>> 2^L - 1
>>
>> where powceil2 ( x) = smallest power 2^S >= x
>
>
> According to theorems mentioned at the start of chapter 3
> of Baker's "Transcendental Number Theory", the following is
> true.
>

(...)


> So ... if I haven't botched the above in any way (which
> I probably have), you "only" need to check a few hundred
> thousand values of L. You'd do that in practice by calculating
> log 3 / log 2 with sufficient accuracy (plain ol' double
> precision should be fine) and looking to see how close to
> an integer you can get by multiplying it by an integer
> up to a few hundred thousand in size.
>

Gareth et.al -

to continue the discussion I invite to join into personal
communication respecting the current repost of the newsgroup-
charter.
I think I have a definite disproof of the above inequality, but
also it could be faulty.

Thanks for all contributions so far -

Gottfried Helms

Ray Steiner

unread,
Jun 1, 2004, 1:41:08 PM6/1/04
to
Gareth McCaughan <gareth.m...@pobox.com> wrote in message news:<c8radh$4ls$1...@news.ks.uiuc.edu>...

There is a paper by Georges Rhin(1987) in which he proves that
|p log 2 - q log 3| > H^(-13.3),

where H = max(p,q) and H > 2.
After that, just check the convergents of log-2(3).
Regards,
Ray Steiner

Ray Steiner

unread,
Jun 1, 2004, 1:48:53 PM6/1/04
to
Gottfried Helms <he...@uni-kassel.de> wrote in message news:<c94mv1$jl8$05$1...@news.t-online.com>...

I proved the nonexistence of a circuit in the 3x+1 problem in 1977.
Is this what a "primitive cycle" actually is? A circuit is a cycle
with one rise and one
fall.

In fact, B. deWeger has recently shown that there is no cycle in the
3x+1 rproblem
with less than 69 rises and falls in it. I can actually extend this to
70 and 71 rises and falls
with Rhin's inequality which I mentioned in an earlier post.
Regards,
Ray Steiner

Gottfried Helms

unread,
Jun 2, 2004, 11:54:37 AM6/2/04
to
Am 01.06.04 19:48 schrieb Ray Steiner:

>>
>> I proved the nonexistence of a circuit in the 3x+1 problem in 1977.
>> Is this what a "primitive cycle" actually is? A circuit is a cycle
>> with one rise and one
>> fall.
>>
>> In fact, B. deWeger has recently shown that there is no cycle in the
>> 3x+1 rproblem
>> with less than 69 rises and falls in it. I can actually extend this to
>> 70 and 71 rises and falls
>> with Rhin's inequality which I mentioned in an earlier post.
>> Regards,
>> Ray Steiner
>>


Hmm, that's interesting. I called it a "primitive", if there
are N-1 steps ascending and 1 step descending, like it is in

(7->11->17) -> 13

which, written as an transfer only noting the occuring
exponents-of-2

13 = T(7;1,1,4)

My question was

"is there any solution in integers x,N,A with

x = T(x;1,1,1,1...1,A) with the 1 (N-1)-times occuring
establishing an N-Step-Loop
".

I found this very tight relation to the 3^N - 2^N properties,
thus my question here.
The case of only one-raise-one-fall, if that means

x = T(x;1,A)

would then just be a special case of my question and can be proven
by enumeration or even modular arithmetic.

But I would like to know, how you accessed the problem of
this specific of rises&falls? I have a formula, how you can
disprove a circle of *any* finite combination of raises&false in
finite number of tests, let say 100 raises&falls by a number
Z of tests, where Z is a combinatorical function of about 42,
which I'm bounding down by optimizing my formulas.
My attempt was to generalize these formulas to *unlimited* Z.

The "primitive" Loop is the most simple structure of that
general problem of unlimited length, and has very tight and handy
relations to the (3/2)^N - structure and that of frac( (3/2)^N),
which I'm currently investigating.

---------------------------

Concerning your reference to deWegner:
His literature looks interesting, especially those with
the focus on binomials: that was the next idea, that I wanted
to step in. As I pointed out in a previor post the related
problem can be represented using a rep-unit-form and the
question, whether 3^n-1 div 2^N can ever be a repunit base
a certain power of 2^P with p reasonably greater than N (don't
have it at hand just now). I'm currently studying, what the binomial-
expansion of 3^N = (2+1)^N explains for that problem.

Just have seen your reference to Rhin: could you point to
a reference?

Regards -

Gottfried Helms

Reply all
Reply to author
Forward
0 new messages