Timeline for Increasing sequences in polynomial progressions modulo p

5 events

when toggle format	what		by	license	comment
Jan 16, 2018 at 6:04	history	edited	Ryan Alweiss		add number theory tag
Jan 13, 2018 at 15:48	comment	added	Ryan Alweiss		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.
Jan 13, 2018 at 1:40	comment	added	Colin Defant		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.
Jan 12, 2018 at 20:23	review	First posts
Jan 12, 2018 at 20:38
Jan 12, 2018 at 20:19	history	asked	Ryan Alweiss	CC BY-SA 3.0