| Texto completo | |
| Autor(es): |
Martins, Rodrigo S. V.
;
Panario, Daniel
;
Qureshi, Claudio
;
Schmutz, Eric
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | 29TH INTERNATIONAL CONFERENCE ON PROBABILISTIC, COMBINATORIAL AND ASYMPTOTIC METHODS FOR THE ANALYSIS OF ALGORITHMS, AOFA 2018; v. 110, p. 11-pg., 2018-01-01. |
| Resumo | |
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 logT 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. (AU) | |
| Processo FAPESP: | 13/25977-7 - Segurança e confiabilidade da informação: teoria e prática |
| Beneficiário: | Marcelo Firer |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 15/26420-1 - Métricas no contexto de Teoria da Informação e códigos corretores de erros |
| Beneficiário: | Claudio Michael Qureshi Valdez |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |