5
$\begingroup$

In a random permutation on $n$ elements one expects the largest increasing and decreasing sequences to have size $(2+o(1))\sqrt{n}$. Is it known if this same property holds in sequences given by polynomial progressions? Say that $p$ is a prime and we consider the map $\pi$ sending $x$ to $x^2$ modulo $p$. Then what is the largest $k$ such that there exists $0 \le a_1< \cdots <a_k$ so that $a_i^2$ are (say, nonstrictly) increasing modulo $p$? What if we instead consider the map $x^{-1}$, or some other polynomial or rational map?

The collisions should not be an important issue in general as there are only $O(1)$ of them at each point, and we can break ties arbitrarily. But in any case, I am curious if these maps modulo $p$ are "psuedorandom" in some sense. My first idea for the polynomial case is to try degree reduction. For $x^2$, this map looks locally linear in that $(x+1)^2-x^2 \equiv 2x+1$ does not vary by much when $x$ varies over an interval of length $o(p)$.

Improve this question
$\endgroup$
2
  • $\begingroup$ I don't think these sequences will give pseudorandom "permutations" because of the "local linearity" you mentioned. Let $L(p)$ be the length $k$ that you are considering. I just computed $L(p)$ for the first $3000$ primes, and it appears as though $L(p)$ is not $(2+o(1))\sqrt p$. In fact, it looks like $\liminf_{p\to\infty}\frac{1}{\sqrt p}L(p)>2.2$. You might try thinking about the sequences explicitly rather than probabilistically, at least in trying to construct long increasing subsequences to give lower bounds for $L(p)$. Probabilistic arguments might still help in finding upper bounds. $\endgroup$
    – Colin Defant
    Commented Jan 13, 2018 at 1:40
  • $\begingroup$ Good catch, although your comment only applies to the squares case. For squares I think $L(p)$ is bigger, because for instance we can use the squares of everything up to $d\sqrt{p}$ and then we expect a $2\sqrt{p(1-d^2)}$ increasing sequence left that is compatible with this. This can yield anything up to $\sqrt{5p}$ although empirical evidence suggests $\sqrt{6p}$ is the answer. For inverses, cubes, fourth powers, and so on, empirical evidence suggests it appears to approach $2\sqrt{p}$. I am pretty sure that squares are the only exceptional case. $\endgroup$
    – Ryan Alweiss
    Commented Jan 13, 2018 at 15:48

0

Reset to default

You must log in to answer this question.