{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T07:04:33Z","timestamp":1776841473609,"version":"3.51.2"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2002,10,9]],"date-time":"2002-10-09T00:00:00Z","timestamp":1034121600000},"content-version":"unspecified","delay-in-days":38,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2002,9]]},"abstract":"<jats:p>Let q be an integer with <jats:italic>q<\/jats:italic> [ges     ] 2. We give a new proof of a result of Erd\u00f6s and Tur\u00e1n \ndetermining the proportion of elements of the finite symmetric group <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> having no cycle of \nlength a multiple of <jats:italic>q<\/jats:italic>. We then extend our methods to the more difficult case of obtaining \nthe proportion of such elements in the finite alternating group <jats:italic>A<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>. In both cases, we derive \nan asymptotic formula with error term for the above mentioned proportion, which contains \nan unexpected occurrence of the Gamma-function.<\/jats:p><jats:p>We apply these results to estimate the proportion of elements of order 2<jats:italic>f<\/jats:italic> in <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, and \nof order 3<jats:italic>f<\/jats:italic> in <jats:italic>A<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> and <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, where gcd(2, <jats:italic>f<\/jats:italic>) = 1, and gcd(3, <jats:italic>f<\/jats:italic>) = 1, respectively, and log <jats:italic>f<\/jats:italic> \nis polylogarithmic in <jats:italic>n<\/jats:italic>. We also give estimates for the probability that the <jats:italic>f<\/jats:italic>th power of \nsuch elements is a transposition or a 3-cycle, respectively. An algorithmic application of \nthese results to computing in <jats:italic>A<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> or <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, given as a black-box group with an order oracle, is \ndiscussed.<\/jats:p>","DOI":"10.1017\/s0963548302005217","type":"journal-article","created":{"date-parts":[[2002,10,11]],"date-time":"2002-10-11T11:48:11Z","timestamp":1034336891000},"page":"447-464","source":"Crossref","is-referenced-by-count":16,"title":["Permutations with Restricted \nCycle Structure and an \nAlgorithmic Application"],"prefix":"10.1017","volume":"11","author":[{"given":"ROBERT","family":"BEALS","sequence":"first","affiliation":[]},{"given":"CHARLES R.","family":"LEEDHAM-GREEN","sequence":"additional","affiliation":[]},{"given":"ALICE C.","family":"NIEMEYER","sequence":"additional","affiliation":[]},{"given":"CHERYL E.","family":"PRAEGER","sequence":"additional","affiliation":[]},{"given":"\u00c1KOS","family":"SERESS","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2002,10,9]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548302005217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T22:08:57Z","timestamp":1554415737000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548302005217\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,9]]},"references-count":0,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2002,9]]}},"alternative-id":["S0963548302005217"],"URL":"https:\/\/doi.org\/10.1017\/s0963548302005217","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,9]]}}}