4
$\begingroup$

Allow me to explain and give examples of something I've been playing around with.

Let $A$ be the $n+1$ tuple of the form $(0, 1, 2, \ldots, n)$. Let $k = n + 1$ be the number of elements.

My question is: is there a tuple $B$ which is a permutation of $A$ that when you multiply element-wise $AB \bmod k$ you get a binary tuple e.g. each element of the tuple $e_i \in \{0,1\}$?

An example is take $$A = (0,1,2), B = (0,1,2)$$ Then $$AB\bmod 3 = (0\cdot0, 1\cdot1, 2\cdot2) \bmod3 = (0, 1, 1)$$ since $0\cdot0 = 0\bmod3, 1\cdot1 = 1\bmod3, 2\cdot2=1\bmod3$. Then this $B$ is a possible solution. Note that $$B = (0,2,1)$$ is not a solution since $$AB\mod{3} = (0\cdot0, 1\cdot2, 2\cdot1)\bmod3 = (0, 2, 2).$$ I have found that up to $k=9$ there is always a permutation. The amount of permutations vary and this is what I have so far for each $k$ using a brute force program:

$$1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 4, 7: 7, 8: 4, 9: 18.$$

An example solution for $k=9$ is to take the permutation $$A = (0,1,2,3,4,5,6,7,8), B = (1, 0, 5, 6, 7, 2, 3, 4, 8)$$ which results in $$AB\mod{9} = (0,0,1,0,1,1,0,1,1).$$

There are some things I can immediately see such as any element can work in the 0th place since it will be multiplied by 0. Whereas only 0 and 1 work in the 1st place. Finding the 0s will happen when $ab\mid k$ and the 1s when $ab$ is coprime to $k$.

What I do not know and would love help on is:

  1. Is there always a permutation that works for any $k > 9$?
  2. Is there a way to find the number of permutations possible for each $k$? Like a formula to describe the sequence of permutation counts?
  3. Is there a way to generate a permutation without brute force?
Improve this question
$\endgroup$
4
  • $\begingroup$ Please use TeX for all mathematical formulae. That is, "$(n+1)$-tuple" instead of "n+1 tuple" etc. Also, explain what you mean by expressions like $2*2$. $\endgroup$ Commented Jun 2, 2024 at 14:22
  • $\begingroup$ @GHfromMO I've edited to have TeX for each math formula. I've also updated the example to be more clear. When I have the expression $2*2$ that is multiplication in the typical way of integers, then taking $\mod{k}$. So when I say $AB$ I am defining multiplying these tuples by multiplying each element by the ith element in the other tuple and taking $\mod{k}$ This means that for any $A,B$ being $k$ tuples their product $AB$ is also a $k$ tuple with every element being in the range of $0, k-1$ $\endgroup$ Commented Jun 2, 2024 at 14:29
  • $\begingroup$ It is better to use standard notation, e.g. $2\cdot 2$ instead of $2*2$. $\endgroup$ Commented Jun 2, 2024 at 14:56
  • 1
    $\begingroup$ @GHfromMO I've corrected the multiplication notation. Thank you for all your feedback. It has been a few years since I was in academia using TeX. $\endgroup$ Commented Jun 2, 2024 at 15:01

2 Answers 2

Reset to default
5
$\begingroup$

Such a permutation exists if and only if $k$ is $1$, $6$, $8$, $p$, or $p^2$ for some prime $p$, and if so, one such permutation has a simple explicit description.

The cases $k=1,6,8$ are easy. If $k=p$ or $k=p^2$, we can use the permutation $$\pi(x)=\begin{cases}x^{-1}&\gcd(x,k)=1,\\x&\text{otherwise.}\end{cases}$$

On the other hand, assume that $\pi$ is such a permutation for a given $k$. Then $$p\ge\varphi(k/p)$$ for all prime factors $p\mid k$: there are $\varphi(k/p)$ elements $x$ such that $\gcd(x,k)=p$, and $\pi$ maps these elements injectively into the set of all elements $y$ such that $py\equiv0\pmod k$, the number of which is $p$.

If $k$ is not a prime power, let $p_1<p_2<\dots<p_l$, $l\ge2$, be its prime divisors; then $$p_1\ge\varphi(k/p_1)\ge(p_2-1)\prod_{i>2}(p_i-1)>p_1$$ unless $l=2$ and $p_2-1=p_1$, i.e., $k=6$.

If $k=p^e$, $e\ge2$, then $$p\ge\varphi(p^{e-1})=p^{e-2}(p-1)>p$$ unless either $e=2$, or $e=3$ and $p=2$, i.e., $k=8$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very nice! It's fun when a question actually has a complete answer. $\endgroup$ Commented Jun 3, 2024 at 13:02
7
$\begingroup$

No. For $n=14$ it's not possible. There are at most $\phi(15)=8$ ones modulo $15$ in the product, and thus a least $15-8=7$ zeros. However, each zero must result from the product of numbers at least one of which is divisible by 5. We have only 6 multiples of 5 in the two permutations and thus getting 7 zeros is not possible.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Thank you for your counter example. I now have a better understanding of finding possible solutions. Your answer makes me think there may be a max $k$ which has a permutation as described and any larger $k$ will not have one because increasing $k$ means "less supply" of zeros and ones. $\endgroup$ Commented Jun 2, 2024 at 15:12
  • 1
    $\begingroup$ @Jacob No, it's more complicated than that. E.g., such a permutation always exists when $k$ is prime. $\endgroup$ Commented Jun 2, 2024 at 16:09
  • $\begingroup$ @EmilJeřábek So I understand how when $k$ is prime you have "best possible chance" of finding a permutation because of the totient function argument above, but how is it known that you'll always have a permutation in this case? Could there not be some prime $k$ where an element $e$ in the tuple has only a couple choices $a,b$ s.t. $ae, eb = 1$ but $a,b$ are "taken"? $\endgroup$ Commented Jun 2, 2024 at 16:34
  • 5
    $\begingroup$ @Jacob: For prime $n+1$, just pair each non-zero element $m$ with $m^{-1}\bmod(n+1)$, and zero with zero. $\endgroup$ Commented Jun 2, 2024 at 16:49
  • $\begingroup$ Ah that makes it clear. Thank you! $\endgroup$ Commented Jun 2, 2024 at 16:55

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.