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$?

  • $\begingroup$ 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. $\endgroup$ – Mariano Suárez-Álvarez Feb 15 '10 at 4:09
  • $\begingroup$ I did not manage but I guess it's fine like this... $\endgroup$ – domotorp Feb 21 '10 at 7:14
  • 1
    $\begingroup$ Surely, you don't mean "$Q_S(m)=2$ if $m\in S$" - that does not define a permutation. $\endgroup$ – Igor Pak Feb 22 '10 at 4:14
  • $\begingroup$ 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... $\endgroup$ – domotorp Feb 22 '10 at 8:25
  • $\begingroup$ 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 $\endgroup$ – 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.

  • $\begingroup$ This seems to be a nice approach, unfortunately I do not understand how you want to apply the even-town theorem, could you write a little more about that? My motivation is the following equivalent formulation of the problem: mathoverflow.net/questions/15204/… $\endgroup$ – domotorp Feb 25 '10 at 10:18
  • $\begingroup$ 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... $\endgroup$ – Igor Pak Feb 25 '10 at 18:01
  • $\begingroup$ So now I see that probably you mean that the orbit of 3 is a cycle such that every element goes to the one that is just bigger than it, the biggest returning to 1. Is this what you mean? I also see that if for the set S defining (the orbit of 3 in) P_i and the set T defining (the orbit of 3 in) P_j we have S\cap T odd, then the orbit of P_iP_j must contain 2. Using the (trivial part of the) even-town theorem I can see that this gives another construction with 2^{n/2} elements. To be continued... $\endgroup$ – domotorp Feb 26 '10 at 22:11
  • $\begingroup$ But I don't see how an upper bound would follow (for your special case) as if the intersection of two sets is even, the orbit of the corresponding functions might still contain 2. Could you say something about that? $\endgroup$ – domotorp Feb 26 '10 at 22:20
  • $\begingroup$ 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. $\endgroup$ – Igor Pak Feb 26 '10 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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