A curious inversion problem

I’ve been exploring a new problem with a couple of students recently that I find incredibly compelling, and I thought I’d mention it here. The main idea is looking at the behavior of functions of the form f(x) = ax + b in various mods. There’s actually a huge amount to explore here, from fixed points to invertibility to the length of loops when you repeatedly apply functions. But one apparent pattern in particular blew me away.

The question is this: in mod n, how many functions f(x)= ax +b are their own inverses?

For example, the function f(x) = 5x + 2, applied twice in mod 12, is equal to the identity. It’s direct to check: f(f(x)) = f(5x+2) = 5(5x+2) + 2 = 25 x + 10 + 2 = x (mod 12).

We proved that there are at least n+1 self-invertible functions of this form for odd n, and n+2 for even n… these are our minimal cases. But what about the non-minimal cases?

We worked out the cases up to 28 by hand, and bewilderingly, for every non-minimal n, the number of self-invertible functions was always a number that completely factored as products of 2s and 3s. For example, in mod 12 there are 24 = 2x2x2x3 linear functions that are their own inverses.

I can see no reason why this should be true, or what these things even have to do with each other. My hunch is that it may just be a coincidence. Still, if it is a coincidence, it’s a pretty marvelous one, working for n = 8, 12, 15, 16, 20, 21, 24, 28, which, by our reckoning, are the non-minimal cases. How long should we expect such a pattern to hold before we suspect that something is going on?

In any case, the behavior of these functions mod n has totally captured me for the time being. I can’t believe I’ve never thought about them with students before.

 

This entry was posted in lesson, Math Musings and tagged , , , , . Bookmark the permalink.

6 Responses to A curious inversion problem

  1. Michael Knapp says:

    Am I misunderstanding the problem? For n=2, I find two solutions, f(x)=x and f(x)=x+1. That’s fewer than n+2. Also, for n=16, I find 28 (divisible by 7) solutions. These are f(x)=ax+b with:
    a=1, b=0, 8
    a=7, b=0, 2, 4, 6, 8, 10, 12, 14
    a=9, b=0, 8
    a=15, b=0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

    Am I missing solutions?

    • Dan says:

      I think you’ve understood it perfectly. We excluded n=2 as a special case, since 1=-1.

      For n=16, we may have miscounted! I appreciate the catch. Your count looks right to me. I’ll double check it tomorrow with my student.

  2. Tom says:

    I also love this problem. Some friends and I have a preprint:

    http://arxiv.org/abs/1205.3207

    This is pretty readable and it has the answer you are looking for (spoiler alert) – see Corollary 4.3.

    • Dan says:

      Thanks! I’ll take a look as soon as I’m not worried about the spoiler anymore :-)

      I spent a little more time with the problem today with my student, and I’ve got some more insight into what the appropriate conjectures should be:

      Let A(n) be the number of functions of the form ax+b that are their own inverse in mod n.

      Conjecture 1. If a and b are relatively prime, then A(ab) = A(a)A(b).

      Conjecture 2. For p an odd prime, A(p^m) = p^m+1.

      If I get a chance to spend a few more minutes, I should be able to write out the rules for powers of 2. I’m pretty sure A(2^m) = 2^m + 2 + 2^(m-1) + 2 = 4(2^(m-2)+2^(m-3)+1). I need to check that one again to make sure I’ve got all the details right.

      In any case, if my conjectures are right–and they look much, much better to me than my old, discredited one, then it shouldn’t be hard to write out a general formula.

  3. Michael Knapp says:

    Dan, I think you’re right except that your formula for A(2^m) only works for m>2. I get something different for A(2) and A(4).

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>