# Two [n] to [n] function families

Note. This question had a bounty, so at the end I accepted the best (and only) answer. However, a solution is implied by the answer to this question.

Question. Fix n. We are interested in the biggest t for which there exist two families of functions, $$P_i,Q_i$$, of size t from [n] to [n] such that for any $$i,j$$ whenever we consider the infinite sequence $$P_i(Q_j(P_i(Q_j\ldots P_i(3))\ldots)$$ (where the number of iterations tends to infinity), it contains no 2's and infinitely many 1's if $$i=j$$ and it contains no 1's and infinitely many 2's if $$i\ne j$$.

A lower bound. I know a construction that shows that $$t\ge 2^{\frac n2-O(1)}.$$ For every subset $$S$$ of [n] that contains exactly one of $$2k$$ and $$2k+1$$ for $$2\le k\le \frac n2-2$$ we construct a pair of functions, $$P_S,Q_S$$ as follows. For any number m denote by $$m^+$$ the smallest element of $$S$$ that is bigger than m or if all elements of $$S$$ are at most m then define it to be 1. $$P_S(1)=1, P_S(2)=2$$ and for bigger $$m$$'s $$P_S(m)=m^+$$, while $$Q_S(1)=1, Q_S(2)=2$$ and for bigger $$m$$'s $$Q_S(m)=m$$ if $$m\in S$$ and $$Q_S(m)=2$$ if $$m\notin S$$. This way we go through all the elements of S and end in 1 if the functions have the same index, but we are pushed to 2 if they differ.

Upper bound. It is of course true that $$t\le n^n$$. So can you do better than $$2^n$$?

• To get bold, you can wrap the text with pairs of asterisks; see daringfireball.net/projects/markdown/syntax#em for a general reference of the notation available. – Mariano Suárez-Álvarez Feb 15 '10 at 4:09
• I did not manage but I guess it's fine like this... – domotorp Feb 21 '10 at 7:14
• Surely, you don't mean "$Q_S(m)=2$ if $m\in S$" - that does not define a permutation. – Igor Pak Feb 22 '10 at 4:14
• You are completely right, I am talking about functions and not permutations everywhere, so I changed permutations to functions, I donno how I could be so stupid. Btw, now I wonder if the original question makes any sense... – domotorp Feb 22 '10 at 8:25
• Please forgive me, but I am only a hobbyist, s I have to ask: what is [n] meaning. Probably it is obvious but I do not know and it is difficult to goggle such symbol... There is at least several meaning which may fit,see: en.wikipedia.org/wiki/Table_of_mathematical_symbols – kakaz Feb 22 '10 at 10:30

Okay, so I tried to see how this could possibly work. After some thinking I decided that one may as well take $P_i=Q_i$, so that the orbit of 3 (under the action of $P_i$) is a cycle containing 1. If you take the length of this cycle to be roughly $n/2$, send $2\to 3$ and everything else to 2, that's not a bad idea except that it doesn't work for all possible $n/2$-subsets; otherwise we would have roughly $\binom{n}{n/2}$ possible $i$, as you wanted to begin with. If you now look at the orbit of 3 under $(P_iP_j)$ in this setting you pretty quickly conclude that there is an inherent "even-town theorem" (see Babai-Frankl's book) and thus $2^{n/2}$ is really the best possible. Of course, in the full generality weird things might be possible - I have no intuition for this, but this doesn't look good and unless the difference is really really important for some applications I wouldn't recommend working on this problem.
• As I said, I considered possible pairs of subsets A,B for which $P_A$ and $P_B$ defined as above satisfy $P_AP_B$ has a 2 orbit cycle. When you do a calculation, this shows $|A\cap B|$ must be even (among other things). All of this is under certain "natural" assumptions, so I don't have any kind of theorem. That would take quite a bit of work, I imagine. Sorry I can't be more clearer and resolve the whole problem... – Igor Pak Feb 25 '10 at 18:01
• Umm, kind of. First, you actually have a freedom of choice which cycle $3\to A\to 1\to 3$ to take - there are many ordering of A. Say you fix one $P_A$. Now you need to take a another, say $P_B$, and try what conditions does it have to satisfy so that $[P_AP_B]^k(3)$ has no 1. I remember concluding that this must satisfy some kind of parity conditions and really similar in form to what you have in the question. But as I said, I didn't formally prove anything - I simply convinced myself that there is no better construction, but you might try going along this route and see where it takes you. – Igor Pak Feb 26 '10 at 23:47