1 Search Results for "Panario, Daniel"


Document
Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes

Authors: Rodrigo S. V. Martins, Daniel Panario, Claudio Qureshi, and Eric Schmutz

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)


Abstract
Let f be a uniformly random element of the set of all mappings from [n] = {1, ..., n} to itself. Let T(f) and B(f) denote, respectively, the least common multiple and the product of the lengths of the cycles of f. Harris proved in 1973 that log T converges in distribution to a standard normal distribution and, in 2011, Schmutz obtained an asymptotic estimate on the logarithm of the expectation of T and B over all mappings on n nodes. We obtain analogous results for uniform random mappings on n = kr nodes with preimage sizes restricted to a set of the form {0,k}, where k = k(r) >= 2. This is motivated by the use of these classes of mappings as heuristic models for the statistics of polynomials of the form x^k + a over the integers modulo p, where k divides p - 1. We exhibit and discuss our numerical results on this heuristic.

Cite as

Rodrigo S. V. Martins, Daniel Panario, Claudio Qureshi, and Eric Schmutz. Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 30:1-30:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{martins_et_al:LIPIcs.AofA.2018.30,
  author =	{Martins, Rodrigo S. V. and Panario, Daniel and Qureshi, Claudio and Schmutz, Eric},
  title =	{{Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{30:1--30:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.30},
  URN =		{urn:nbn:de:0030-drops-89237},
  doi =		{10.4230/LIPIcs.AofA.2018.30},
  annote =	{Keywords: random mappings with indegree restrictions, Brent-Pollard heuristic, periods of mappings}
}
  • Refine by Author
  • 1 Martins, Rodrigo S. V.
  • 1 Panario, Daniel
  • 1 Qureshi, Claudio
  • 1 Schmutz, Eric

  • Refine by Classification
  • 1 Mathematics of computing → Enumeration

  • Refine by Keyword
  • 1 Brent-Pollard heuristic
  • 1 periods of mappings
  • 1 random mappings with indegree restrictions

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail