On pseudo-polynomials divisible only by a sparse set of primes and α-primary pseudo-polynomials Kuperberg, Vivian Zieve Pseudo-polynomials Chinese remainder theorem Ruzsa’s conjecture We explore two questions about pseudo-polynomials, which are functions f : N → Z such that k divides f(n + k) − f(n) for all n, k. First, for certain arbitrarily sparse sets R, we construct pseudo-polynomials f with p|f(n) for some n only if p ∈ R. This implies that not all pseudo-polynomials satisfy an assumption of a recent paper of Kowalski and Soundararajan. We also consider α-primary pseudo-polynomials, where the pseudo-polynomial condition is only required for k lying in a set of primes of density α. We show that if an α-primary pseudo-polynomial is O(e(β−)n), where β = √7 3 − 1 6 ≈ 0.715, then it is a polynomial. Elsevier 2022 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_2df8fbb1 https://research-explorer.ista.ac.at/record/22196 Kuperberg VZ. On pseudo-polynomials divisible only by a sparse set of primes and α-primary pseudo-polynomials. <i>Journal of Number Theory</i>. 2022;241:531-541. doi:<a href="https://doi.org/10.1016/j.jnt.2022.04.006">10.1016/j.jnt.2022.04.006</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jnt.2022.04.006 info:eu-repo/semantics/altIdentifier/issn/0022-314X info:eu-repo/semantics/altIdentifier/arxiv/2006.02527 info:eu-repo/semantics/openAccess