## Table of LCM’s vs. table of products

In 2004 Kevin Ford established sharp asymptotics on Erdős’ problem on the number of different products a⋅b, a,b∈{1,…,n}. (http://arxiv.org/abs/math/0401223, see also discussion here: Number of elements in the set {1,⋯,n}⋅{1,⋯,n}) My naive question is whether there are much less different numbers of the form lcm(a,b), where a,b∈{1,…,n}. Answer AttributionSource : Link , Question Author : … Read more

## Conjectured new primality test for Mersenne numbers

How to prove that this conjecture about a new primality test for Mersenne numbers is true ? Definition: Let M_{q}=2^{q}-1 , S_{0} = 3^{2} + 1/3^{2} , \ and: \ S_{i+1} = S_{i}^{2}-2 \pmod{M_{q}} Conjecture: M_{q}\text{ is a prime iff: } \ S_{q-1} \equiv S_{0} \pmod{M_{q}} \text{ and iff: } \prod_{0}^{q-2} S_i \equiv 1 \pmod{M_{q}} … Read more

## Integer solution

For every prime p, does there exists integers x1, x2 and x3 (0≤x1,x2,x3≤⌊cp1/3⌋ and c is some large constant) such that p−12−⌊2cp1/3⌋≤f(x1,x2,x3)≤p−12, where, f(x1,x2,x3)=x1+x2+x3+2(x1x2+x2x3+x3x1)+4x1x2x3. Answer I doubt that the lower bound p−12−2cp1/3 holds for all p. Here is a proof for the weaker bound p−12−cp1/2. First of all, the inequality p−12−cp1/2≤f(x1,x2,x3)≤p−12 is essentially equivalent to … Read more

## Smooth admissible representations, Hom, tensor and extension of scalars

(Remark: This has previously been posted on math.stackexchange, but I believe it might be suitable for this site as well. https://math.stackexchange.com/questions/1428350/smooth-admissible-representations-hom-tensor-and-extension-of-scalars ) Let G be a locally profinite group, and consider V and W smooth admissible representations of G over some field F (or char. 0). Let E/F be any field extension. I’d like to … Read more

## Shifted convolution problem for Coefficients of automorphic forms

The shifted convolution problem for coefficients of modular forms is well studied and many estimates were established for the shifted convolution sums of Hecke eigenvalues. So, one may ask about the generalization of these estimates to the case of automorphic forms: Are there analogue estimates for the shifted convolution sums of automorphic forms? Thank you. … Read more

## Behavior of the “mean prime factor” of numbers

This question concerns the behavior of a function f() that maps each number in N to its mean prime factor. I previously posted premature questions, now deleted, which explains the cites below to several who contributed observations. Also, the question, “Distribution of the number of prime factors,” may be relevant. Define f(n) to be the … Read more

## A problem on prime numbers

Given integers a,b,c,d∈[2n,2m] with m>n>1, how many primes p are there in [nα,nβ] for some 1<α<β such that 0<amod 0<b\bmod p<n^{\alpha/k} 0<c\bmod p<n^{\alpha/l} 0<d\bmod p<n^{\alpha/l} holds where k,l>2 is fixed? Assume n,m,\alpha,\beta,k,l are fixed. Heuristically we can solve for average case of choice of a,b,c,d following way: \frac{|\{p:a\bmod p<n^{\alpha/k}\}|}{|\{p:p\in[n^\alpha,n^\beta]\}|}\approx\frac{|\{p:b\bmod p<n^{\alpha/k}\}|}{|\{p:p\in[n^\alpha,n^\beta]\}|}\approx\frac{n^{\alpha/k}}{(n^{\beta}-n^\alpha)/\log(n^{\beta}-n^\alpha)} \frac{|\{p:c\bmod p<n^{\alpha/l}\}|}{|\{p:p\in[n^\alpha,n^\beta]\}|}\approx\frac{|\{p:d\bmod p<n^{\alpha/l}\}|}{|\{p:p\in[n^\alpha,n^\beta]\}|}\approx\frac{n^{\alpha/l}}{(n^{\beta}-n^\alpha)/\log(n^{\beta}-n^\alpha)} So \mathsf{Prob}(a\bmod … Read more

## The probability distribution of LCM of uniformly distributed integers in {1,…,n}\{1,\ldots,n\}

In the recent paper by Fernandez and Fernandez here on ArXiv, the following formula which was first proved by Diaconis and Erdos appears, on page 2. For 0<t≤1 the distribution of the lcm of independent pairs of integers X1,X2 uniformly drawn from {1,…,n} satisfies: P(lcm(X1,X2)≤tn2)=1−1ζ(2)⌊1t⌋∑j=11−jt(1−ln(jt))j2+Ot(lnnn). The authors extend these results to k>2, but I am … Read more

## Relations between Mirimanoff polynomials

Let p be a prime number ≥5, let fi(X) be the i-th Mirimanoff polynomial (with respect to p) : fi(X)=X+2i−1X2+…+(p−1)i−1Xp−1. Mirimanoff noted that the three polynomials fp−1(X),fp−1(1−X) and −Xpfp−1(1−1/X) are congruent modulo p. He also gave relations between fp−1(X),fp−2(X),fp−2(1−X) and −Xpfp−2(1−1/X), for example : f_{p-1}(X)^2 \equiv – 2 X^p f_{p-2}(X) – 2 (1 – X^p) … Read more

## Is this a viable public key cryptosystem?

Would this, or a variant, work as a public key cryptosystem? Alice takes a (computable) function p of several variables, let us say p(x,y). We can think of p as a polynomial and x and y as integers but the variables could easily be other objects such as matrices over the complex numbers. She chooses … Read more