Halbeisen, L. A number-theoretic conjecture and its implication for set theory. (English) Zbl 1138.11302 Acta Math. Univ. Comen., New Ser. 74, No. 2, 243-254 (2005). Let \(|\text{seq}^ {1-1}(S)|\) denote the cardinality of the set of all finite one-to-one sequences that can be formed from elements of a given set \(S\), and for positive integers \(a\) let \(|a^S|\) denote the cardinality of all functions from \(S\) to \(a\). The author and S. Shelah [J. Symbolic Logic 59, 30–30 (1994; Zbl 0795.03064)] proved that for infinite sets \(S\) one always has \(|\text{seq}^ {1-1}(S)|\neq |2^S|\), but nothing more can be proved without the axiom of choice. The aim of the paper is to state and give evidence for a number-theoretical conjecture which implies that for any infinite set \(S\) and for every integer \(a\geq 2\), \(|\text{seq}^ {1-1}(S)|\neq |a^S|\). Before stating the conjecture we need some definitions. For any non-negative integer \(n\), let \(n^*\) be the number of one-to-one sequences we can build with \(n\) distinct objects. Further let \(D(a)=\{n<a\:a|n^*\}\) and \(d(a)=|D(a)|\). A positive integer \(a\) is called \(1\)-regular if \(d(a)\leq 1\). (In the paper various statistical results about the distribution of \(1\)-regular integers, or about the random behavior of \(n^*\) or \(D(a)\) can also be found.) For every integer \(a\geq 2\) let \(P_a=n\:n^*=n^k\;\text{for\;some}\;k\geq 2\) and \(P_a=\cup _{a\geq 2}^\infty P_a\). The author formulates the following three conjectures: (A) The set \(P\) is finite. (B) For each integer \(a\geq 2\), the set \(P_a\) is finite. (C) For each integer \(a\geq 2\), the set \(n\:n^*=a^k\;\text{for\;some}\;k\geq 2\;\text{and}\^^M(n+t)\in P_a\;\text{for\;some}\;1\leq t\leq k\) is finite (in the paper the words “is finite” are missing in the formulation of the last conjecture). Actually it is the weakest of the three conjectures the Conjecture C which is mainly used in the paper. One of the results of the paper says that if Conjecture C is true, then for any infinite set \(S\) and any integer \(a\geq 2\) we always have \(|\text{seq}^ {1-1}(S)|\neq |a^S|\), even in the absence of the axiom of choice. Reviewer: Štefan Porubský (Prague) MSC: 11A25 Arithmetic functions; related numbers; inversion formulas 03E05 Other combinatorial set theory 03E65 Other set-theoretic hypotheses and axioms 11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors 11B83 Special sequences and polynomials Keywords:finite non-repetitive sequences; axiom of choice; sequence A000522; shadow; set cardinality; Zermelo-Fraenkel set theory; combinatorial number theory Citations:Zbl 0795.03064 PDFBibTeX XMLCite \textit{L. Halbeisen}, Acta Math. Univ. Comen., New Ser. 74, No. 2, 243--254 (2005; Zbl 1138.11302) Full Text: EuDML EMIS Online Encyclopedia of Integer Sequences: Number of solutions to x^4 == 0 (mod n). a(n) is the number of unitary divisors of n (d such that d divides n, gcd(d, n/d) = 1). Number of odd unitary divisors of n. d is a unitary divisor of n if d divides n and gcd(d,n/d)=1. Number of distinct shadow transforms for sequences of length n.