Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let us consider the following operation on positive integers: $$n=\prod_{i=1}^{k}p_i^{\alpha_i} \qquad f(n):= \prod_{i=1}^{k}\alpha_ip_i^{\alpha_i-1}$$ (Is it true that if we apply this operation to any integer multilpe times, it will eventually get into a finite cycle?) Is there a constant $K$ such that any integer will fall into a cycle after $K$ steps?

Edit4: We managed to settle affirmatively the question of Mark Sapir, whether a cycle of arbitrary length exists: http://www.math.bme.hu/~kovacsi/Pub/arithmetic_derivation_v04.pdf

Edit3: I proposed two questions (in retrospect, it was a minor mistake), one of them was answered. To appreciate this, i accept Mark Sapir's answer, and alter the original text by putting the unanswered stuff into parentheses. Making the answered one the main question.

Edit2: István Kovács pointed out that there is a nice formula for $f(n)$ using the 'number of divisors' function: $$ f(n):= d \left( \frac{n}{ \prod_{i=1}^{n}p_i } \right) \frac{n}{ \prod_{i=1}^{n}p_i } $$ from which it fillows that for any $\varepsilon >0 , \quad f(n)=o(n^{1+\varepsilon})$.

I think that the answer to the first question is yes, but to the second no. We tested the first $10000$ integers and every integer fell into a cycle after at most $6$ steps.

Edit: @MarkSapir proved that the answer to the second question is no. His proof raises the (third) question: How long can such a cycle be?

share|improve this question
5  
I suspect $p^{p^p}$ and so on will need several steps before hitting a cycle so the answer to the second question should be no. For example $3^{27}$ takes $10$ steps before hitting a fixed point. –  Felipe Voloch Sep 21 '13 at 16:34
4  
Note that this differs from the usual arithmetic derivative en.wikipedia.org/wiki/Arithmetic_derivative. –  Martin Brandenburg Sep 22 '13 at 11:29
    
Why wouldn't you make it distributive over products of primes: seems a bit more natural? –  Lev Borisov Sep 22 '13 at 11:54
    
A similar question is mathoverflow.net/questions/25974/calculus-on-rationals. –  Roland Bacher Feb 1 at 23:15

4 Answers 4

up vote 22 down vote accepted

I will show that the answer to the second question is "no". Note that if the answer to the first question is "no", we are done. Hence assume that the answer is "yes" and for every number $n$, the chain eventually turns into a cycle. Take any number $n$ and consider a sequence of numbers $n, f(n)(n-1), f(f(n)(n-1))(n-2),...$, that is $a_1=n, a_{m+1}=f(a_m)(n-m)$, for every $m=1,...,n-1$. Let $A=a_n$. Let $p$ be a prime that is bigger than any number that occurs in the chain for $A$. Consider $p^n$. Then the chain for $p^n$ looks like $p^n\to a_1p^{n-1}\to ...\to a_n\to...$ and the chain for $A=a_n$ follows. That chain will never hit the first $n$ of the numbers in the chain for $p^n$, hence the chain for $p^n$ does not go into a cycle before the step number $n$. Since $n$ was arbitrary, we are done. This answers the second question. The first question seems more difficult.

Edit. As @DanielSoltész pointed out, I answered a harder question about bounding the length of a pre-cycle in the chain $m\to f(m)\to\ldots$. If we want to show that there is no bound for the number of different elements in a chain, then assuming $p>n^{2^n-1}$ is enough. This leads to another reasonable question about bounding the lengths of cycles $m\to...\to m$. That question is open.

share|improve this answer
    
How do you ensure that after the first $n$ steps the chain doesn't go back to some $f^k(p^n)$, $k<n$ ? –  BS. Sep 22 '13 at 7:14
1  
I don't see either how $p>n^n$ ensures that, but it can be done. You just consider the sequence without powers of $p$: $$1→n→f(n)(n−1)→f(f(n)(n−1))(n−2)→...$$ and you choose a prime greater than every element in it. Thank you Mark Sapir, for the elegant solution. (Also by observing $f(n)<n^2$ one could obtain a bound on $p$, but this isn't enough to prove that $n^n$ is enough.) –  Daniel Soltész Sep 22 '13 at 8:58
    
I replaced $n^n$ by $n^{2^n}$. Hope it is enough. I first wanted to write simply $p\gg n$ (which is clearly enough for what I wrote). But @BS's comment is in fact relevant. One needs to prove also that the chain does never produces an extra power of $p$. I have to think about it. –  Mark Sapir Sep 22 '13 at 11:31
    
@BS: I changed the answer again. $n^n$ may not be enough but there is a bound anyway (although we may never know what it is). –  Mark Sapir Sep 22 '13 at 11:50
    
@MarkSapir : nice trick! –  BS. Sep 22 '13 at 12:11

While working on the first question, i managed to get another solution to the second, different from Mark's. Consider the formal product: $$P_0=\prod_{p_i \, prime} p_{i}^{p_i}.$$ Note that it is the fixed point of the formal derivation. Then the formal derivative of $2P_0$ is $f(2P_0)=3P_0$. In general it is true that $f^{(k)}(2P_0)=c_k f^{(k-1)}(2P_0)$ for a $c_k>1$. Indeed as every exponent is at least as big as its base. Thus lets formally derive $2P_0$, k-times. Then there are only finitely many primes which had their exponents changed during the process. Removing every other prime from $2P_0$ we obtain a finite product which has its first $k$ derivatives strictly increasing.

share|improve this answer

I did some computations with the integers up to 400000 and I got the following conclusions:

1) The following are cycles with more than one element (i.e. non-fixed points)

  • [32,80]=[2⁵, 2⁴·5]
  • [864,2160]=[2⁵·3³, 2⁴·3³·5]
  • [708588,2598156,787320]=[2²·3¹¹, 2²·3¹⁰·11, 2³·3⁹·5]
  • [5832,17496,61236,20412]=[2³·3⁶, 2³·3⁷, 2²·3⁷·7, 2²·3⁶·7]

2) All the integers up to 400000 end up falling in a fix point or one of the previous cycles (or maybe another 2-cycle that I have missed) except for $2^{16}$, $2^{17}$, $2^{16}\cdot 3$, $2^{16}\cdot 5$, $2^{18}$, $2^{17}\cdot 3$, $2^{12}\cdot 3^4$, $2^4\cdot 3^9$, $2^9\cdot 3^6$.

These exceptional values end up reaching some number that my computer cannot handle. As an example the first six exceptional values (all of those with the exponent of 2 being bigger or equal to 16) lead to $2^{18}\cdot 3^5$, which after 10 more steps or so computed by hand keeps increasing and doesn't look like falling into a cycle soon. This agrees with Felipe's comment.

3) I found all the above using bad programming: I computed the actual numbers instead of keeping track of primes and exponents as one does by hand. Reprogramming everything using this idea should give much better results.

Addendum 1: Studying the case $2^{16}$ I could find some more 2-cycles, such as

  • $[2^{63}\cdot 3^{13}\cdot 7\cdot 31,2^{62}\cdot 3^{14}\cdot 7\cdot 13]$ ($2^{16}$ reaches this 2-cycle after 33 steps).
  • $[2^{279}\cdot 3^{61}\cdot 31\cdot 139,2^{278}\cdot 3^{62}\cdot 31\cdot 61]$
  • $[2^{15}\cdot 3^{33}\cdot 7\cdot 17,2^{14}\cdot 3^{34}\cdot 5\cdot 11]$

The left term of all of them is of the form $2^{2p+1}\cdot 3^{2q-1}\cdot p\cdot q$ with $(2p+1)(2q-1)=9\cdot c$ where $p,q$ are primes different from $2,3$ and $c$ is a square-free integer coprime with $2,3$. More generally we have the following.

Let $p,q,r,s$ be pairwise distinct primes such that $(pr+1)(ps-1)=q^2\cdot c$ where $c$ is a square-free integer coprime with $p,q$. Then $[p^{pr}\cdot q^{ps}\cdot c,p^{pr+1}\cdot q^{ps-1}\cdot r\cdot s]$ is a $2$-cycle of $f$.

N.B.: If $r,s\neq 2$, the hypothesis force either $p=2$ or $q=2$. So a much easier result is:

Let $p>2,3$ be a prime such that $2p=3c+1$, where $c$ is a square-free integer coprime with $3$. Then $[2^3\cdot 3^{2p-1}\cdot p,2^2\cdot 3^{2p}\cdot c]$ is a $2$-cycle of $f$.

E.g. $p=11,17,29,47,53$ do the trick.

Addendum 2: I have already coded everything properly (please tell me if you are interested in the code). At the moment I'm looking for cycles as long as possible. If found out some 5-cycles and 6-cycles: for example 2²·3⁴⁷·5⁶ is the beginning of a 5-cycle and 2⁶⁷·3¹⁰⁵·5⁵·53·67 is the beginning of a 6-cycle. Of course one wonders if there are cycles of arbitrary length and how to find them. It would be nice to find a proposition extending the one I gave in Addendum 1 to $f^k$ for arbitrary $k$.

Addendum 3: I got similar results for $k=4$:

Let $p>2,3$ be a prime such that $6p+1$ is a square-free integer. Then $[2^3\cdot 3^{6p}\cdot p, 2^3\cdot 3^{6p+1}\cdot p, 2^2\cdot 3^{6p+1}\cdot (6p+1),2^2\cdot 3^{6p}\cdot(6p+1)]$ is a $4$-cycle of $f$.

All the primes between 5 and 97 satisfy the conditions of this proposition except for 29 and 79.

Let $p>2,3$ be a prime such that $p-1=6c$ for a square-free integer $c$. Then $[2^2\cdot 3^p\cdot p, 2^2\cdot 3^{p-1}\cdot p, 2^3\cdot 3^{p-1}\cdot c, 2^3\cdot 3^p\cdot c]$ is a $4$-cycle of $f$.

Some primes which satisfy the conditions are 31, 43, 67 and 79.

share|improve this answer
1  
Cycles of arbitrary length exists, see the link after Edit4 in the original post. We also have a proper computer program. We will check whether your cycle construction is covered by our work. But this may take some time. –  Daniel Soltész Sep 1 at 17:01
    
I don't know how I could miss that link. Great job indeed. If you think my computations can be useful to you in some way, don't hesitate to tell me. –  A. Bellmunt Sep 1 at 19:42

Here's an elementary observation inspired by Felipe's insightful comment.

Let's attack a simpler version of this problem and try to engineer long cycles when the starting point is $n = p^{k_0}$ for some $k_0 > 1$. Starting with such an $n$, we immediately see that $f(n) = k_0p^{k_0-1}$ and so we try to establish some control over the prime factors of $k_0$. In order to keep things as simple as possible, we might want $k_0$ to again be a power of $p$, say $k_0 = p^{k_1}$ so that we are left with $f(n) = p^{k_1 + k_0 -1}$. So long as $k_1 > 1$, we are guaranteed $f(n) \neq n$.

Proceeding in this fashion, it seems as though we are after a sequence $k_j$ of integers which satisfy the following property: denoting the partial sums as $K_j = \sum_{0 \leq i < j}k_j$, we want $$k_j = p^{K_j - j}.$$

In order to ensure a cycle of length $L+1$, we would want a contiguous subsequence $k_j, \ldots , k_{j+L}$ so that the set of shifted partial sums $$\{K_{j+i} - (j+i) \mid 0 \leq i \leq L\}$$ has cardinality $L+1$. I'm not sure how one goes about finding such a sequence $k_j$, but hopefully there are number theory wizards out there who know such things...

share|improve this answer
2  
I don't understand this answer either! If $k_0=p^{k_1}$ then except for some trivial cases, it cannot be that $k_0+k_1-1$ is a power of $p$. So I don't understand what ``proceeding in this fashion" means. –  Lucia Sep 21 '13 at 22:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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