Search Results

Documents authored by Martins, Rodrigo S. V.

Document
DOI: 10.4230/LIPIcs.AofA.2018.30
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.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}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact