A new theorem about aliquot sequences - Page 2

Raman · 2012-05-26, 20:48

Quote:

Originally Posted by Raman

Thus, it translates into
"Has the Collatz Conjecture been proved? Is it being true? It states that any starting number when repeatedly multiplied by three, and then added one, terminates in one. It appears to me that it is being very likely for this(it) to be true."

For example, for some starting number N, repeatedly iterating the 3x+1 function one can try out to prove off something
thereby establishing an upper bound result that the intermediate number value will not (cannot) go beyond N.2^k at all.

Oops, sorry, a major correction please.

It states that if the number is odd, then multiply by 3, and then add 1,
if it is even, then divide by 2.
If this process is being continued again and again, then taking any starting number will eventually end in 1 always.

I think that it is not being very tough in order to prove this fact,

There are more being chances for this to be true, in turn
that's what I will feel it repeatedly, in fact

Quote:

Take any starting number. If it is odd, then multiply by three and then add one. If it is even, then divide by two. If this process is continued, every number will eventually terminate in one. I feel that it is very likely for this to be true. I think that it is very easy to prove this, as well.

முக்கியமான திருத்தம்

ஏதாவது எண்ணை எடுத்துக்கொண்டு தொடங்குங்கள். அதை ஒற்றைப்படையாக இருந்தால், மூன்றால் பெருக்கிவிட்டு, ஒன்றை சேருங்கள். இரட்டைப்படையாக இருந்தால், இரண்டால் வகுங்கள். இந்த செயலை தொடர்ந்தால், எல்லாம் எண்களும் எப்பொழுதும் இறுதியில் ஒன்றில் வந்து முடிவடையும் என்று இந்த ஊகம் குறிக்கிறது. நான் இதை உண்மையாக இருக்க அதிக வாய்ப்புகள் இருக்கிறது என்று நினைக்கிறேன். அது போல், இதை நிரூபிக்கவும் மிகவும் எளிதாக இருக்கும் என்று எனக்கு தோன்றுகிறது.

சரி?

Dubslow · 2012-05-26, 21:16

Quote:

Originally Posted by Raman

Oops, sorry, a major correction please.

It states that if the number is odd, then multiply by 3, and then add 1,
if it is even, then divide by 2.
If this process is being continued again and again, then taking any starting number will eventually end in 1 always.

I think that it is not being very tough in order to prove this fact,

There are more being chances for this to be true, in turn
that's what I will feel it repeatedly, in fact

முக்கியமான திருத்தம்

ஏதாவது எண்ணை எடுத்துக்கொண்டு தொடங்குங்கள். அதை ஒற்றைப்படையாக இருந்தால், மூன்றால் பெருக்கிவிட்டு, ஒன்றை சேருங்கள். இரட்டைப்படையாக இருந்தால், இரண்டால் வகுங்கள். இந்த செயலை தொடர்ந்தால், எல்லாம் எண்களும் எப்பொழுதும் இறுதியில் ஒன்றில் வந்து முடிவடையும் என்று இந்த ஊகம் குறிக்கிறது. நான் இதை உண்மையாக இருக்க அதிக வாய்ப்புகள் இருக்கிறது என்று நினைக்கிறேன். அது போல், இதை நிரூபிக்கவும் மிகவும் எளிதாக இருக்கும் என்று எனக்கு தோன்றுகிறது.

சரி?

If it was easy, someone would have done it.

garambois · 2012-05-26, 21:23

Quote:

Originally Posted by R. Gerbicz

There are serious problems with the proof of lemma 5 (2nd article) even for cases where m is prime. As I can see you are trying to determine the complementer event: if q==-1 mod m and q|n and q^2 doesn't divide n then m|sigma(n).

But there are cases you left out in the counting: let m=5 and 2^3|n and 2^4 doesn't divide n you can get that sigma(2^3)=15 divides sigma(n), so 5 also divides sigma(n) but 2==-1 mod 5 is not true.

For composites m there are much more problems with the proof.

You are wrong !
It's a problem because the demonstration is in french. And the translation on the forum is wrong.

If q divides n and q don't divide n^2 then :
If n=qA and q and A are coprime

Then :
sigma(n)=(1+q) sigma(A)

And because q==-1[m] then m will divide (q+1)
So m will divide sigma(n)

You have to take q==-1[m], it is written in the french demonstration.

Did you read the french demonstration or the english demonstration on the forum before posting this message ???

Jean-Luc

Dubslow · 2012-05-26, 21:46

I'm working on making a (hopefully half decent) translation of the first PDF. I don't understand the first sentence of the proof of theorem 1. "Soient k 2 e/qui vaut m Ak". What's the 'e/qui'? Does it mean something like "Let k>=2 _along with_ an m \in A_k"?

Another note: In the first paragraph, it defines A_k for all l >= 1, but I don't see an l in the definition of the set. (Also, I think there's a typo 'pout' -> 'pour' in there.)

Also, it's slow going because half the time is spent reproducing the tex.

R. Gerbicz · 2012-05-26, 22:21

Quote:

Originally Posted by garambois

It's a problem because the demonstration is in french. And the translation on the forum is wrong.

OK, your proof is correct, though not checked every line and my French is poor. But I understand your idea, its nice.

Dubslow · 2012-05-26, 23:19

http://www.aliquotes.com/Aliquote.pdf
I can't offer any commentary at all on the mathematics of it; I'm just a messenger

(I still don't really understand the first sentence of the proof of Theorem 1.)

I'd be willing to translate the second PDF, but it might go faster if I didn't have to reproduce all the TeX... (hint hint

)
Edit: It's much fancier. This might take a while, but it'll be an interesting challenge. Can I get access to the original *TeX please?

My last note is to be careful about super- and sub-scripts; this forum's TeX-renderer can't handle multiple nested levels of supers/subs very well. I'd recommend reading this simultaneously with the original PDF -- the su*s are clearer there.

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

Let $p_k$ be the k-th prime number. Let $t_1 = 2$ and for all $k \ge 1$ , let $t_{k+1} = \phi\left(p^{t_k+1}_k\cdot(p_{k+1}-1)\right)-1$ where $\phi$ is the Euler function. For all $l\ge1$ , let $A_k = \left{m\quad |\quad for\quad all \quad1\le i\le k\quad val_p_i(m) = t_i\right}$ be the set of integers whose factorization starts with the "driver" $p^{t_1}_1...p^{t_k}_k$ . Let $s(m)=\sigma(m)-m$ .

Theorem 1 (Lenstra 76): For all $k\ge2$ , if $m\in A_k$ , then $s(m) \in A_{k-1}$ .

Proof: Let $k \ge 2$ with $m \in A_k$ . Then there exists a prime $B \in \mathbb{N}$ with $p_1,...,p_k$ such that $m=p^{t_1}_1...p^{t_k}_kB$ . We note that $s(m)=\sigma(p^{t_1}_1)...\sigma(p^{t_k}_k)B-p^{t_1}_1...p^{t_k}_kB$ . We show that for all $1\le i\le k-1$ , $\sigma(p^{t_{i+1}}_{i+1})$ is divisible by $p^{t_i+1}_i$ . We have $\sigma(p^{t_{i+1}}_{i+1})=\frac {p^{t_{i+1}+1}_{i+1}-1} {p_{i+1}-1}$ which in turn equals $\frac {p^{\phi\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)}_{i+1}-1} {p_{i+1}-1}$ by construction of $t_{i+1}$ . Recall Fermat's little theorem: for all $n \in \mathbb{N}$ and a such that $gcd(a,n)=1$ we have $a^{\phi(n)}-1\equiv 0\quad mod\quad n$ . We apply the theorem with $a=p_{i+1}$ and $n=\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)$ and we obtain $p^{\phi\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)}_{i+1}-1\equiv 0\quad mod\quad \left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)$ , which is equivalent to $p^{t_i+1}_i\quad |\quad \sigma(p^{t_{i+1}}_{i+1})$ . We directly deduce that $val_p_i(s(m))=t_i$ . Thus $s(m) \in A_{k-1}$ .

Corollary 1 (Garambois' 2nd conjecture): For all $k>1$ and all $l\in \mathbb{N}$ , there exists an Aliquot sequence such that for $l$ consecutive iterations, $\frac {s(m)} {m} > k$ .

Proof: We use Mertens' formula $\sum_{p\quad prime,\quad p\le x}\frac {1} {p}\quad \sim\quad log\quad log\quad x$ . In particular, $\sum_{p\quad prime} \frac{1}{p}$ diverges and the product $\prod_{p\quad prime}(1+\frac{1}{p})$ goes to infinity. Therefore there exists an $n \in \mathbb{N}$ such that $\prod_{i=1}^{n}(1+\frac{1}{p_i})>k+1$ . We choose an element $m_0$ of $A_{n+l}$ . By Lensta's theorem, the first $l+1$ iterations of the Aliquot sequence starting at $m_0$ are respectively in $A_{n+l},\quad A_{n+l-1},...,A_n$ . Let $k \in [0,l]$ ; then $m\quad:=s^k(m_0)$ is in $A_{n+k}$ and thus can be written as $p^{t_1}_1...p^{t_{n+k}}_{n+k}B$ for an integer $B$ coprime to $p_1,...,p_{n+k}$ . We have $\frac {s(m)}{m}=\frac{\sigma(m)}{m}-1$ and $\frac{\sigma(m)}{m}=\frac{\sigma(B)}{B}\prod_{i=1}^{n+k}(1+\frac{1}{p_i}+...+\frac{1}{p^{t_i}_i})\quad\ge\quad \frac{\sigma(B)}{B}\prod_{i=1}^{n+k}(1+\frac{1}{p_i})\quad \ge\quad \frac{\sigma(B)}{B}\prod_{i=1}^n (1+\frac{1}{p_i})$ which is larger than $\frac{\sigma(B)}{B}(k+1)$ by our choice of $n$ . Finally, $\sigma(B)$ is the sum of the divisors of $B$ , here including $B$ , so $\sigma(B)>B$ . Thus $\frac{\sigma(m)}{m}>k+1$ , whence we conclude $\frac{s(m)}{m}>k$ .

R. Gerbicz · 2012-05-26, 23:45

Quote:

Originally Posted by Dubslow

http://www.aliquotes.com/Aliquote.pdf
I can't offer any commentary at all on the mathematics of it; I'm just a messenger

(I still don't really understand the first sentence of the proof of Theorem 1.)

Thanks for the translation! So val_{p_i}(m)=t_i means that the exact p_i power divisor of m is p_i^t_i. You give no definition just explaining it with the driver.

The proof is good, but if you know Lenstra's theorem then this proof is really triviality.

Dubslow · 2012-05-27, 05:36

Title: "On the density of integers n divisible by a certain integer m such that m does not divide $\sigma(n)-n$ ."

1 Introduction

"The purpose of this paper is to present the proof of a theorem concerning the density of integers n divisible by a certain integer m such that m doesn't divide $\sigma(n)-n$ . We will demonstrate that this density is null by giving the asymptotic density of these numbers n less than a real x."

Translator's note: Hmm.. there's some way to translate this that I'm missing. Asymptotic complexity?

2 Notations and Definitions

"In all of the following:
Let $m$ be a fixed natural integer $\ge$ 3.
$x$ and $t$ will designate positive real numbers.
We define sum-of-divisors and sum-of-proper-divisors functions like so:
$\begin{align}\sigma(n)=\sum_{d|k}d.\end{align}$
And
$\begin{align}\sigma^\prime(n)=\sigma(n)-n.\end{align}$
and we also define the function $\phi(n)$ : Euler's totient function which counts the number of integers $\le$ that are coprime to $n$ ."

TN: There's a typo: "et on défnit" -> "et on définit"

3 Theorem 1

"The (asymptotic) density of the integers n divisible by m such that m doesn't divide $\sigma^\prime(n)$ ( $=\sigma(n)-n$ ) is null (0). Further, we give the following [asymptotic density]|[asymptotic complexity] for any sufficiently large real number x:

$A_m(x)\quad := card\left{ n\le x\quad such\quad that\quad m|n\quad and\quad m\dagger\sigma^\prime(n)\right}=\mathcal{O}\left(\frac{x}{\left(\ln\ln x\right)^{\frac{1}{\phi(m)}}}\right)$ .

TN: Sorry about the dagger, I couldn't find a "does not divide" symbol that the forum would render.
TN2: I guess I'll slowly translate the thing over the course of a few days or something, then copy and paste the tex into one post.

firejuggler · 2012-05-27, 05:53

As I said earlier, I shouldn't try to translate math-involving thing.

Dubslow · 2012-05-27, 05:55

Quote:

Originally Posted by firejuggler

As I said earlier, I shouldn't try to translate math-involving thing.

I don't understand the math either.

Quote:

Originally Posted by R. Gerbicz

So val_{p_i}(m)=t_i means that the exact p_i power divisor of m is p_i^t_i. You give no definition just explaining it with the driver.

I assume you're talking to the OP?

Quote:

Originally Posted by R. Gerbicz

The proof is good, but if you know Lenstra's theorem then this proof is really triviality.

I suppose that's why he called it a corollary

garambois · 2012-05-27, 10:40

Quote:

Originally Posted by garambois

You are wrong !
It's a problem because the demonstration is in french. And the translation on the forum is wrong.

If q divides n and q^2 don't divide n then :
If n=qA and q and A are coprime

Then :
sigma(n)=(1+q) sigma(A)

And because q==-1[m] then m will divide (q+1)
So m will divide sigma(n)

You have to take q==-1[m], it is written in the french demonstration.

Did you read the french demonstration or the english demonstration on the forum before posting this message ???

Jean-Luc

I'm sorry but it was an error in the text !

Wrong (old post) :
If q divides n and q don't divide n^2 then :

Right :
If q divides n and q^2 don't divide n then :

Jean-Luc

2012-05-26, 23:19	#17
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	Here's a stab at translating the first PDF http://www.aliquotes.com/Aliquote.pdf I can't offer any commentary at all on the mathematics of it; I'm just a messenger (I still don't really understand the first sentence of the proof of Theorem 1.) I'd be willing to translate the second PDF, but it might go faster if I didn't have to reproduce all the TeX... (hint hint ) Edit: It's much fancier. This might take a while, but it'll be an interesting challenge. Can I get access to the original TeX please? My last note is to be careful about super- and sub-scripts; this forum's TeX-renderer can't handle multiple nested levels of supers/subs very well. I'd recommend reading this simultaneously with the original PDF -- the sus are clearer there. ----------------------------------------------------------- Let $p_k$ be the k-th prime number. Let $t_1 = 2$ and for all $k \ge 1$ , let $t_{k+1} = \phi\left(p^{t_k+1}_k\cdot(p_{k+1}-1)\right)-1$ where $\phi$ is the Euler function. For all $l\ge1$ , let $A_k = \left{m\quad \|\quad for\quad all \quad1\le i\le k\quad val_p_i(m) = t_i\right}$ be the set of integers whose factorization starts with the "driver" $p^{t_1}_1...p^{t_k}_k$ . Let $s(m)=\sigma(m)-m$ . Theorem 1 (Lenstra 76): For all $k\ge2$ , if $m\in A_k$ , then $s(m) \in A_{k-1}$ . Proof: Let $k \ge 2$ with $m \in A_k$ . Then there exists a prime $B \in \mathbb{N}$ with $p_1,...,p_k$ such that $m=p^{t_1}_1...p^{t_k}_kB$ . We note that $s(m)=\sigma(p^{t_1}_1)...\sigma(p^{t_k}_k)B-p^{t_1}_1...p^{t_k}_kB$ . We show that for all $1\le i\le k-1$ , $\sigma(p^{t_{i+1}}_{i+1})$ is divisible by $p^{t_i+1}_i$ . We have $\sigma(p^{t_{i+1}}_{i+1})=\frac {p^{t_{i+1}+1}_{i+1}-1} {p_{i+1}-1}$ which in turn equals $\frac {p^{\phi\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)}_{i+1}-1} {p_{i+1}-1}$ by construction of $t_{i+1}$ . Recall Fermat's little theorem: for all $n \in \mathbb{N}$ and a such that $gcd(a,n)=1$ we have $a^{\phi(n)}-1\equiv 0\quad mod\quad n$ . We apply the theorem with $a=p_{i+1}$ and $n=\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)$ and we obtain $p^{\phi\left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)}_{i+1}-1\equiv 0\quad mod\quad \left(p^{t_i+1}_i\cdot(p_{i+1}-1)\right)$ , which is equivalent to $p^{t_i+1}_i\quad \|\quad \sigma(p^{t_{i+1}}_{i+1})$ . We directly deduce that $val_p_i(s(m))=t_i$ . Thus $s(m) \in A_{k-1}$ . Corollary 1 (Garambois' 2nd conjecture): For all $k>1$ and all $l\in \mathbb{N}$ , there exists an Aliquot sequence such that for $l$ consecutive iterations, $\frac {s(m)} {m} > k$ . Proof: We use Mertens' formula $\sum_{p\quad prime,\quad p\le x}\frac {1} {p}\quad \sim\quad log\quad log\quad x$ . In particular, $\sum_{p\quad prime} \frac{1}{p}$ diverges and the product $\prod_{p\quad prime}(1+\frac{1}{p})$ goes to infinity. Therefore there exists an $n \in \mathbb{N}$ such that $\prod_{i=1}^{n}(1+\frac{1}{p_i})>k+1$ . We choose an element $m_0$ of $A_{n+l}$ . By Lensta's theorem, the first $l+1$ iterations of the Aliquot sequence starting at $m_0$ are respectively in $A_{n+l},\quad A_{n+l-1},...,A_n$ . Let $k \in [0,l]$ ; then $m\quad:=s^k(m_0)$ is in $A_{n+k}$ and thus can be written as $p^{t_1}_1...p^{t_{n+k}}_{n+k}B$ for an integer $B$ coprime to $p_1,...,p_{n+k}$ . We have $\frac {s(m)}{m}=\frac{\sigma(m)}{m}-1$ and $\frac{\sigma(m)}{m}=\frac{\sigma(B)}{B}\prod_{i=1}^{n+k}(1+\frac{1}{p_i}+...+\frac{1}{p^{t_i}_i})\quad\ge\quad \frac{\sigma(B)}{B}\prod_{i=1}^{n+k}(1+\frac{1}{p_i})\quad \ge\quad \frac{\sigma(B)}{B}\prod_{i=1}^n (1+\frac{1}{p_i})$ which is larger than $\frac{\sigma(B)}{B}(k+1)$ by our choice of $n$ . Finally, $\sigma(B)$ is the sum of the divisors of $B$ , here including $B$ , so $\sigma(B)>B$ . Thus $\frac{\sigma(m)}{m}>k+1$ , whence we conclude $\frac{s(m)}{m}>k$ . Last fiddled with by Dubslow on 2012-05-26 at 23:33

2012-05-27, 05:36	#19
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	For those who don't know an ounce of French... Title: "On the density of integers n divisible by a certain integer m such that m does not divide $\sigma(n)-n$ ." 1 Introduction "The purpose of this paper is to present the proof of a theorem concerning the density of integers n divisible by a certain integer m such that m doesn't divide $\sigma(n)-n$ . We will demonstrate that this density is null by giving the asymptotic density of these numbers n less than a real x." Translator's note: Hmm.. there's some way to translate this that I'm missing. Asymptotic complexity? 2 Notations and Definitions "In all of the following: Let $m$ be a fixed natural integer $\ge$ 3. $x$ and $t$ will designate positive real numbers. We define sum-of-divisors and sum-of-proper-divisors functions like so: $\begin{align}\sigma(n)=\sum_{d\|k}d.\end{align}$ And $\begin{align}\sigma^\prime(n)=\sigma(n)-n.\end{align}$ and we also define the function $\phi(n)$ : Euler's totient function which counts the number of integers $\le$ that are coprime to $n$ ." TN: There's a typo: "et on défnit" -> "et on définit" 3 Theorem 1 "The (asymptotic) density of the integers n divisible by m such that m doesn't divide $\sigma^\prime(n)$ ( $=\sigma(n)-n$ ) is null (0). Further, we give the following [asymptotic density]\|[asymptotic complexity] for any sufficiently large real number x: $A_m(x)\quad := card\left{ n\le x\quad such\quad that\quad m\|n\quad and\quad m\dagger\sigma^\prime(n)\right}=\mathcal{O}\left(\frac{x}{\left(\ln\ln x\right)^{\frac{1}{\phi(m)}}}\right)$ . TN: Sorry about the dagger, I couldn't find a "does not divide" symbol that the forum would render. TN2: I guess I'll slowly translate the thing over the course of a few days or something, then copy and paste the tex into one post. Last fiddled with by Dubslow on 2012-05-27 at 05:55 Reason: adding part 2

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Broken aliquot sequences	fivemack	FactorDB	46	2021-02-21 10:46
Broken aliquot sequences	schickel	FactorDB	18	2013-06-12 16:09
poaching aliquot sequences...	Andi47	FactorDB	21	2011-12-29 21:11
Asymptotic properties of Aliquot sequences	Lothar	Homework Help	1	2011-03-29 09:23
New article on aliquot sequences	schickel	mersennewiki	0	2008-12-30 07:07

2012-05-26, 21:46	#15
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	I'm working on making a (hopefully half decent) translation of the first PDF. I don't understand the first sentence of the proof of theorem 1. "Soient k 2 e/qui vaut m Ak". What's the 'e/qui'? Does it mean something like "Let k>=2 _along with_ an m \in A_k"? Another note: In the first paragraph, it defines A_k for all l >= 1, but I don't see an l in the definition of the set. (Also, I think there's a typo 'pout' -> 'pour' in there.) Also, it's slow going because half the time is spent reproducing the tex.

2012-05-27, 05:53	#20
firejuggler "Vincent" Apr 2010 Over the rainbow 2²×7×103 Posts	As I said earlier, I shouldn't try to translate math-involving thing.