For which primes does this iterated function act transitively? (Sort of a finite analogue of Collatz conjecture.)

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
5
down vote

favorite












Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property holds, but upon closer inspection it holds for some primes and not others and now I am wondering if this "elementary" problem is known/studied somewhere or perhaps it is an open problem--I have no idea since I only stumbled into it entirely accidentally. Even learning what area it should be considered, what potential tools there are for studying it, and what else it might be related to (even just keywords to search for!) would be helpful.



The problem statement: Let $p$ be an odd prime and consider the permutation of the set $1,ldots,fracp-12$ defined by sending $n$ to $fracn2$ if $n$ is even and sending it to $fracp-n2$ if $n$ is odd. For which primes $p$ does this permutation have a single orbit?



Here are some examples of iterating this function:



$p=7$) $1 mapsto 3 mapsto 2 mapsto 1$, so it is transitive.



$p=11$) $1 mapsto 5 mapsto 3 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=13$) $1 mapsto 6 mapsto 3 mapsto 5 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=17$) $1 mapsto 8 mapsto 4 mapsto 2 mapsto 1$: here there are two orbits of size 4.



This reminds at least loosely in spirit of the Collatz conjecture but I presume (and hope!) it is much simpler since for each $p$ there are only finitely many numbers to consider. We tried some computer experiments and found lots of primes for which there is a single orbit and also lots for which there is not; we put the sequence of "good" primes in the OEIS and did not find any matches, which makes me suspect there is not something simple like a congruence condition on the prime, but I don't know any number theory so I really have no idea.










share|cite|improve this question

















  • 2




    Reverse it. You are finding primes where 2 is (is not) a primitive root mod p. Gerhard "Now You Search The Literature" Paseman, 2018.10.11.
    – Gerhard Paseman
    5 hours ago










  • Upon reflection (pun intended) it is a little more complicated. I still think primitive root applies. Gerhard "Not Ready For Palindromic Signature" Paseman, 2018.10.11.
    – Gerhard Paseman
    4 hours ago










  • @GerhardPaseman: already the example $p = 7$ shows that this is not what's going on. The function acts transitively modulo $7$, but $2$ is obviously not a primitive root.
    – R. van Dobben de Bruyn
    4 hours ago






  • 1




    The length of the orbit is the order of 2 modulo p if that order is odd, otherwise it's half the order.
    – Felipe Voloch
    4 hours ago










  • Link to the sequence in OEIS?
    – Gerry Myerson
    17 mins ago














up vote
5
down vote

favorite












Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property holds, but upon closer inspection it holds for some primes and not others and now I am wondering if this "elementary" problem is known/studied somewhere or perhaps it is an open problem--I have no idea since I only stumbled into it entirely accidentally. Even learning what area it should be considered, what potential tools there are for studying it, and what else it might be related to (even just keywords to search for!) would be helpful.



The problem statement: Let $p$ be an odd prime and consider the permutation of the set $1,ldots,fracp-12$ defined by sending $n$ to $fracn2$ if $n$ is even and sending it to $fracp-n2$ if $n$ is odd. For which primes $p$ does this permutation have a single orbit?



Here are some examples of iterating this function:



$p=7$) $1 mapsto 3 mapsto 2 mapsto 1$, so it is transitive.



$p=11$) $1 mapsto 5 mapsto 3 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=13$) $1 mapsto 6 mapsto 3 mapsto 5 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=17$) $1 mapsto 8 mapsto 4 mapsto 2 mapsto 1$: here there are two orbits of size 4.



This reminds at least loosely in spirit of the Collatz conjecture but I presume (and hope!) it is much simpler since for each $p$ there are only finitely many numbers to consider. We tried some computer experiments and found lots of primes for which there is a single orbit and also lots for which there is not; we put the sequence of "good" primes in the OEIS and did not find any matches, which makes me suspect there is not something simple like a congruence condition on the prime, but I don't know any number theory so I really have no idea.










share|cite|improve this question

















  • 2




    Reverse it. You are finding primes where 2 is (is not) a primitive root mod p. Gerhard "Now You Search The Literature" Paseman, 2018.10.11.
    – Gerhard Paseman
    5 hours ago










  • Upon reflection (pun intended) it is a little more complicated. I still think primitive root applies. Gerhard "Not Ready For Palindromic Signature" Paseman, 2018.10.11.
    – Gerhard Paseman
    4 hours ago










  • @GerhardPaseman: already the example $p = 7$ shows that this is not what's going on. The function acts transitively modulo $7$, but $2$ is obviously not a primitive root.
    – R. van Dobben de Bruyn
    4 hours ago






  • 1




    The length of the orbit is the order of 2 modulo p if that order is odd, otherwise it's half the order.
    – Felipe Voloch
    4 hours ago










  • Link to the sequence in OEIS?
    – Gerry Myerson
    17 mins ago












up vote
5
down vote

favorite









up vote
5
down vote

favorite











Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property holds, but upon closer inspection it holds for some primes and not others and now I am wondering if this "elementary" problem is known/studied somewhere or perhaps it is an open problem--I have no idea since I only stumbled into it entirely accidentally. Even learning what area it should be considered, what potential tools there are for studying it, and what else it might be related to (even just keywords to search for!) would be helpful.



The problem statement: Let $p$ be an odd prime and consider the permutation of the set $1,ldots,fracp-12$ defined by sending $n$ to $fracn2$ if $n$ is even and sending it to $fracp-n2$ if $n$ is odd. For which primes $p$ does this permutation have a single orbit?



Here are some examples of iterating this function:



$p=7$) $1 mapsto 3 mapsto 2 mapsto 1$, so it is transitive.



$p=11$) $1 mapsto 5 mapsto 3 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=13$) $1 mapsto 6 mapsto 3 mapsto 5 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=17$) $1 mapsto 8 mapsto 4 mapsto 2 mapsto 1$: here there are two orbits of size 4.



This reminds at least loosely in spirit of the Collatz conjecture but I presume (and hope!) it is much simpler since for each $p$ there are only finitely many numbers to consider. We tried some computer experiments and found lots of primes for which there is a single orbit and also lots for which there is not; we put the sequence of "good" primes in the OEIS and did not find any matches, which makes me suspect there is not something simple like a congruence condition on the prime, but I don't know any number theory so I really have no idea.










share|cite|improve this question













Background: I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property holds, but upon closer inspection it holds for some primes and not others and now I am wondering if this "elementary" problem is known/studied somewhere or perhaps it is an open problem--I have no idea since I only stumbled into it entirely accidentally. Even learning what area it should be considered, what potential tools there are for studying it, and what else it might be related to (even just keywords to search for!) would be helpful.



The problem statement: Let $p$ be an odd prime and consider the permutation of the set $1,ldots,fracp-12$ defined by sending $n$ to $fracn2$ if $n$ is even and sending it to $fracp-n2$ if $n$ is odd. For which primes $p$ does this permutation have a single orbit?



Here are some examples of iterating this function:



$p=7$) $1 mapsto 3 mapsto 2 mapsto 1$, so it is transitive.



$p=11$) $1 mapsto 5 mapsto 3 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=13$) $1 mapsto 6 mapsto 3 mapsto 5 mapsto 4 mapsto 2 mapsto 1$, so it is transitive.



$p=17$) $1 mapsto 8 mapsto 4 mapsto 2 mapsto 1$: here there are two orbits of size 4.



This reminds at least loosely in spirit of the Collatz conjecture but I presume (and hope!) it is much simpler since for each $p$ there are only finitely many numbers to consider. We tried some computer experiments and found lots of primes for which there is a single orbit and also lots for which there is not; we put the sequence of "good" primes in the OEIS and did not find any matches, which makes me suspect there is not something simple like a congruence condition on the prime, but I don't know any number theory so I really have no idea.







nt.number-theory prime-numbers permutations collatz-conjecture






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 5 hours ago









Noah Giansiracusa

7343711




7343711







  • 2




    Reverse it. You are finding primes where 2 is (is not) a primitive root mod p. Gerhard "Now You Search The Literature" Paseman, 2018.10.11.
    – Gerhard Paseman
    5 hours ago










  • Upon reflection (pun intended) it is a little more complicated. I still think primitive root applies. Gerhard "Not Ready For Palindromic Signature" Paseman, 2018.10.11.
    – Gerhard Paseman
    4 hours ago










  • @GerhardPaseman: already the example $p = 7$ shows that this is not what's going on. The function acts transitively modulo $7$, but $2$ is obviously not a primitive root.
    – R. van Dobben de Bruyn
    4 hours ago






  • 1




    The length of the orbit is the order of 2 modulo p if that order is odd, otherwise it's half the order.
    – Felipe Voloch
    4 hours ago










  • Link to the sequence in OEIS?
    – Gerry Myerson
    17 mins ago












  • 2




    Reverse it. You are finding primes where 2 is (is not) a primitive root mod p. Gerhard "Now You Search The Literature" Paseman, 2018.10.11.
    – Gerhard Paseman
    5 hours ago










  • Upon reflection (pun intended) it is a little more complicated. I still think primitive root applies. Gerhard "Not Ready For Palindromic Signature" Paseman, 2018.10.11.
    – Gerhard Paseman
    4 hours ago










  • @GerhardPaseman: already the example $p = 7$ shows that this is not what's going on. The function acts transitively modulo $7$, but $2$ is obviously not a primitive root.
    – R. van Dobben de Bruyn
    4 hours ago






  • 1




    The length of the orbit is the order of 2 modulo p if that order is odd, otherwise it's half the order.
    – Felipe Voloch
    4 hours ago










  • Link to the sequence in OEIS?
    – Gerry Myerson
    17 mins ago







2




2




Reverse it. You are finding primes where 2 is (is not) a primitive root mod p. Gerhard "Now You Search The Literature" Paseman, 2018.10.11.
– Gerhard Paseman
5 hours ago




Reverse it. You are finding primes where 2 is (is not) a primitive root mod p. Gerhard "Now You Search The Literature" Paseman, 2018.10.11.
– Gerhard Paseman
5 hours ago












Upon reflection (pun intended) it is a little more complicated. I still think primitive root applies. Gerhard "Not Ready For Palindromic Signature" Paseman, 2018.10.11.
– Gerhard Paseman
4 hours ago




Upon reflection (pun intended) it is a little more complicated. I still think primitive root applies. Gerhard "Not Ready For Palindromic Signature" Paseman, 2018.10.11.
– Gerhard Paseman
4 hours ago












@GerhardPaseman: already the example $p = 7$ shows that this is not what's going on. The function acts transitively modulo $7$, but $2$ is obviously not a primitive root.
– R. van Dobben de Bruyn
4 hours ago




@GerhardPaseman: already the example $p = 7$ shows that this is not what's going on. The function acts transitively modulo $7$, but $2$ is obviously not a primitive root.
– R. van Dobben de Bruyn
4 hours ago




1




1




The length of the orbit is the order of 2 modulo p if that order is odd, otherwise it's half the order.
– Felipe Voloch
4 hours ago




The length of the orbit is the order of 2 modulo p if that order is odd, otherwise it's half the order.
– Felipe Voloch
4 hours ago












Link to the sequence in OEIS?
– Gerry Myerson
17 mins ago




Link to the sequence in OEIS?
– Gerry Myerson
17 mins ago










1 Answer
1






active

oldest

votes

















up vote
4
down vote













It's easier to work with the inverse permutation. Starting from $1$ and working backwards we end up with a sequence $1=2^0to pm 2^1to pm 2^2to cdots topm 2^fracp-12=1$. Where the signs are uniquely determined so that $pm 2^rin 1,2,dots,fracp-12$. This cycle covers all numbers in $1,2,dots,fracp-12$ exactly once if and only if $2^rneq pm 1pmodp$ for any $1le rle fracp-32$.



Proposition: This happens precisely when either $2$ is a primitive root for $p$, or if $p=7pmod 8$ and $2$ has order $fracp-12$.



Proof: In the situation that $2^fracp-12=-1pmodp$ we have that $2^r$ for $r=1,2,cdots, p-1$ forms a complete system of residues, therefore $2$ is a primitive root for $p$. We are left with the case where $2^fracp-12=1pmodp$. This means that $2$ has order $fracp-12$ in $mathbb Z/pmathbb Z$ and moreover $-1$ is not of the form $2^rpmodp$. In turn, this implies $2$ is the square of a primitive root, and so $2^r$ covers all quadratic residues which means $-1$ is not a quadratic residue. Since $left(frac2pright)=1$ and $left(frac-1pright)=-1$ we have $p=7pmod 8$.






share|cite|improve this answer




















    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "504"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f312625%2ffor-which-primes-does-this-iterated-function-act-transitively-sort-of-a-finite%23new-answer', 'question_page');

    );

    Post as a guest






























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    4
    down vote













    It's easier to work with the inverse permutation. Starting from $1$ and working backwards we end up with a sequence $1=2^0to pm 2^1to pm 2^2to cdots topm 2^fracp-12=1$. Where the signs are uniquely determined so that $pm 2^rin 1,2,dots,fracp-12$. This cycle covers all numbers in $1,2,dots,fracp-12$ exactly once if and only if $2^rneq pm 1pmodp$ for any $1le rle fracp-32$.



    Proposition: This happens precisely when either $2$ is a primitive root for $p$, or if $p=7pmod 8$ and $2$ has order $fracp-12$.



    Proof: In the situation that $2^fracp-12=-1pmodp$ we have that $2^r$ for $r=1,2,cdots, p-1$ forms a complete system of residues, therefore $2$ is a primitive root for $p$. We are left with the case where $2^fracp-12=1pmodp$. This means that $2$ has order $fracp-12$ in $mathbb Z/pmathbb Z$ and moreover $-1$ is not of the form $2^rpmodp$. In turn, this implies $2$ is the square of a primitive root, and so $2^r$ covers all quadratic residues which means $-1$ is not a quadratic residue. Since $left(frac2pright)=1$ and $left(frac-1pright)=-1$ we have $p=7pmod 8$.






    share|cite|improve this answer
























      up vote
      4
      down vote













      It's easier to work with the inverse permutation. Starting from $1$ and working backwards we end up with a sequence $1=2^0to pm 2^1to pm 2^2to cdots topm 2^fracp-12=1$. Where the signs are uniquely determined so that $pm 2^rin 1,2,dots,fracp-12$. This cycle covers all numbers in $1,2,dots,fracp-12$ exactly once if and only if $2^rneq pm 1pmodp$ for any $1le rle fracp-32$.



      Proposition: This happens precisely when either $2$ is a primitive root for $p$, or if $p=7pmod 8$ and $2$ has order $fracp-12$.



      Proof: In the situation that $2^fracp-12=-1pmodp$ we have that $2^r$ for $r=1,2,cdots, p-1$ forms a complete system of residues, therefore $2$ is a primitive root for $p$. We are left with the case where $2^fracp-12=1pmodp$. This means that $2$ has order $fracp-12$ in $mathbb Z/pmathbb Z$ and moreover $-1$ is not of the form $2^rpmodp$. In turn, this implies $2$ is the square of a primitive root, and so $2^r$ covers all quadratic residues which means $-1$ is not a quadratic residue. Since $left(frac2pright)=1$ and $left(frac-1pright)=-1$ we have $p=7pmod 8$.






      share|cite|improve this answer






















        up vote
        4
        down vote










        up vote
        4
        down vote









        It's easier to work with the inverse permutation. Starting from $1$ and working backwards we end up with a sequence $1=2^0to pm 2^1to pm 2^2to cdots topm 2^fracp-12=1$. Where the signs are uniquely determined so that $pm 2^rin 1,2,dots,fracp-12$. This cycle covers all numbers in $1,2,dots,fracp-12$ exactly once if and only if $2^rneq pm 1pmodp$ for any $1le rle fracp-32$.



        Proposition: This happens precisely when either $2$ is a primitive root for $p$, or if $p=7pmod 8$ and $2$ has order $fracp-12$.



        Proof: In the situation that $2^fracp-12=-1pmodp$ we have that $2^r$ for $r=1,2,cdots, p-1$ forms a complete system of residues, therefore $2$ is a primitive root for $p$. We are left with the case where $2^fracp-12=1pmodp$. This means that $2$ has order $fracp-12$ in $mathbb Z/pmathbb Z$ and moreover $-1$ is not of the form $2^rpmodp$. In turn, this implies $2$ is the square of a primitive root, and so $2^r$ covers all quadratic residues which means $-1$ is not a quadratic residue. Since $left(frac2pright)=1$ and $left(frac-1pright)=-1$ we have $p=7pmod 8$.






        share|cite|improve this answer












        It's easier to work with the inverse permutation. Starting from $1$ and working backwards we end up with a sequence $1=2^0to pm 2^1to pm 2^2to cdots topm 2^fracp-12=1$. Where the signs are uniquely determined so that $pm 2^rin 1,2,dots,fracp-12$. This cycle covers all numbers in $1,2,dots,fracp-12$ exactly once if and only if $2^rneq pm 1pmodp$ for any $1le rle fracp-32$.



        Proposition: This happens precisely when either $2$ is a primitive root for $p$, or if $p=7pmod 8$ and $2$ has order $fracp-12$.



        Proof: In the situation that $2^fracp-12=-1pmodp$ we have that $2^r$ for $r=1,2,cdots, p-1$ forms a complete system of residues, therefore $2$ is a primitive root for $p$. We are left with the case where $2^fracp-12=1pmodp$. This means that $2$ has order $fracp-12$ in $mathbb Z/pmathbb Z$ and moreover $-1$ is not of the form $2^rpmodp$. In turn, this implies $2$ is the square of a primitive root, and so $2^r$ covers all quadratic residues which means $-1$ is not a quadratic residue. Since $left(frac2pright)=1$ and $left(frac-1pright)=-1$ we have $p=7pmod 8$.







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 4 hours ago









        Gjergji Zaimi

        59.8k3154296




        59.8k3154296



























             

            draft saved


            draft discarded















































             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f312625%2ffor-which-primes-does-this-iterated-function-act-transitively-sort-of-a-finite%23new-answer', 'question_page');

            );

            Post as a guest













































































            Popular posts from this blog

            How to check contact read email or not when send email to Individual?

            Displaying single band from multi-band raster using QGIS

            How many registers does an x86_64 CPU actually have?