Questions tagged [multiplicative-number-theory]
The multiplicative-number-theory tag has no summary.
40 questions
13 votes
2 answers
536 views
What's the probability that two numbers share the same totient function value?
Denoting by $\phi$ the Euler totient function, I am interested in the sequence of probabilities $$P(N):=\frac1{N^2}\big|\big\{(n,m)\in[N]^2:\phi(n)=\phi(m)\big\}\big|.$$ Question 1: Does $P(N)\to0$? ...
- 1,896
0 votes
1 answer
268 views
Evaluating a sum in multiplicative number theory
My question is basically asking for possible explanations to a long calculation that doesn't work out as I expect. Suppose $f$ is a multiplicative arithmetic function which satisfies $$f(p^t)=f(p)=:1+...
- 1,564
11 votes
2 answers
1k views
A lower bound for the radical of a number
How to prove that $$ \operatorname{Rad}(n)\geq n^{\omega (n)/\Omega (n)} \quad\text{for almost all $n\leq x$} \tag{$*$} \label{eq:primes} $$ as $x \to \infty$ where $\omega (n)$ is the number of ...
- 631
0 votes
0 answers
142 views
How strong is cancellation in a smooth triple-character twist?
Fix parameters $$ 0<\varepsilon<\tfrac1{100},\qquad \tfrac12<\vartheta\le\kappa<1, $$ and let $f\colon\mathbb N\to\mathbb C$ be any multiplicative function with $\lvert f(n)\rvert\le 1$. ...
2 votes
0 answers
95 views
Efficiently Updating Matrix Multiplication Result When One Matrix Changes [closed]
Suppose you have two matrices $A \in Z_q^{m\times l}$ and $B \in Z_q^{l\times n}$, and the product $A\cdot B$ has already been computed. Now, matrix $B$ remains unchanged, but a few elements in matrix ...
- 57
2 votes
1 answer
250 views
Why is $\sum_{n=1}^\infty \frac{\sigma_a(pn)}{n^s}=(1+p^a-p^{a-s}) \zeta(s) \zeta(s-a)$ only when $p$ is a prime number?
I tried to find the summation for $a,b\in N$ and $s>a+1$ $$ \Omega_a(b,s)=\sum_{n=1}^\infty \frac{\sigma_a(bn)}{n^s}$$ where $\sigma_a(n)$ is sum of positive divisors function which defined by $$ \...
- 711
0 votes
0 answers
557 views
Is the Conjecture of Representing Integers as Differences of Semiprimes and Primes Extendable to Products of Distinct Primes?
Conjecture: Let $k$ and $l$ be fixed distinct positive integers ($k≠l$). Then, for every positive integer $n$, there exist prime numbers $p_1,p_2,…,p_k∈\mathbb{P}$ and $q_1,q_2,…,q_l∈\mathbb{P}$ such ...
- 17
2 votes
1 answer
242 views
Sums of multiplicative functions over residue classes
It was stated in this Shiu, P. work, page 169, Theorem 2, that $$\sum_{\substack{n\le x\\ n\equiv a\pmod k}}d_r^{\ell}(n)\ll\frac{x}{k}\left(\frac{\phi(k)}{k}\log x\right)^{r^{\ell}-1}.$$ Here, $d_r(n)...
user536681
1 vote
0 answers
243 views
Is it in theory possible to create a subexponential algorithm for solving discrete logarithms in multiplicative subgroups or within an Integer range?
As far I understand, when it comes to finite fields, Pollard rho and Pollard’s lambda are still the best algorithm for solving discrete logarithms in a multiplicative subgroup/suborder…. Index ...
- 129
4 votes
1 answer
475 views
Möbius square root function: existence of multiplicative and bounded function
With $\mu$ being the Möbius function, there exist infinite possibilities of square roots. For example, for each $n$ such that $\mu(n)\neq 0$ there is a choice: if $\mu(n)=-1$, we can choose to define $...
- 75
31 votes
0 answers
905 views
Is it true that $\left\{\frac{\sigma(n)}{\varphi(n)}:\ n\in\mathbb{Z}_{\geq 1}\right\}=\{r\in\mathbb Q:\ r\ge1\}$?
For any positive integer $n$, let $\sigma(n)$ be the sum of all positive divisors of $n$. Clearly, $\sigma(n)\ge n\ge \varphi(n)$ for all $n\in\mathbb{Z}_{\geq 1}$, where $\varphi$ is Euler's totient ...
- 17.6k
4 votes
2 answers
335 views
Sum of $\frac{1}{(\delta_1,\delta_2)}$ with congruence restrictions
In the course of my work, I encountered the following sum ($(x,y)$ stands for the GCD of $x$ and $y$): $$L(Q)=\sum_{\substack{\delta_1,\delta_2\leq Q\\\delta_1\equiv0\ (a)\\\delta_2\equiv0\ (b)}}\frac{...
- 41
2 votes
0 answers
75 views
What lower bounds are known on growth of the distribution of the abundancy index?
Let $a(n)=\sigma(n)/n$ be the abundancy index of $n$ and let $F(x)$ be the distribution function of this index: i.e., the proportion of integers $n$ with $a(n)\leq x$. (This function is well-defined ...
- 2,148
5 votes
2 answers
748 views
"Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$
Given an integer $a$, I would like to build a table of entries $(p, \text{ord}_p(a))$, where $p$ runs over the prime numbers not dividing $a$ and not exceeding a fixed parameter $P$, and $\text{ord}_p(...
- 53
1 vote
0 answers
68 views
Classes of functions which are not almost divisible by a part of the Euler phi function
Given, $f$ and $g$ as functions with domain and range in the integers, we will write $S(f,g)$ to be the set of $n$ such that $f(n)|g(n)$. We will write $f^2$ to just be $f(n)^2$. We will say that $f$ ...
- 8,395
6 votes
1 answer
223 views
Mean value of the divisor function over Piatetski-Shapiro sequences
Let $c>1$, $c\not\in\mathbb{Z}$ and consider the sum $$ \sum_{n\leq x} \tau(\lfloor n^c \rfloor), $$ where $\tau(n)$ is the number of divisors of $n$. I'm almost certain I've seen an evaluation of ...
- 2,142
4 votes
0 answers
156 views
Average of $\lambda(n+1)$ for $n$ smooth, or smooth-and-rough? What follows?
Let $\lambda$ be the Liouville function, i.e., $\lambda(p_1\dotsb p_k)=(-1)^k$ for $p_1,\dotsc,p_k$ not necessarily distinct. There is a conjecture (due to whom?) that there are infinitely many primes ...
- 21.7k
5 votes
1 answer
280 views
Results using a certain kind of identity
Recently, I've been reading about asymptotics for smooth numbers as well as smooth numbers in arithmetic progressions. One of the ideas I find especially pleasing among some of these results is the ...
- 2,142
3 votes
0 answers
255 views
Numbers made up of primes from a given set
Take a set $\mathcal P$ of primes and denote by $\langle \mathcal P\rangle $ the set of all natural numbers composed of primes from $\mathcal P$. If \[ \sum _{p\in \mathcal P}\frac {1}{p}\] converges ...
- 1,564
0 votes
0 answers
90 views
Function multiplicativity
Is this a multiplicative function? $ \displaystyle \sum_{a=1 \atop (a,q)=1}^{q}e^{-2\pi i\frac{a}{q}c_q(da)F}=T(q)$,where $d,F\in \mathbb{N}$ and $c_q(da)$ - Ramanujan's sum https://en.m.wikipedia.org/...
- 1
7 votes
0 answers
191 views
Recovering basic information about perfect numbers from a Dirichlet series
The following question is inspired mostly by this question, answer and the comment by Wojowu there A naive approach to understanding odd perfect numbers is to make a Dirichlet series where the $n$th ...
- 8,395
4 votes
1 answer
435 views
On a sharp version of Halasz's theorem
I am trying to read the following paper by Granville-Harper-Soundararajan and I had a few questions regarding the paper. They prove, for $S(x):=\sum_{n\leq x}f(n)$ and $F_x(s):=\prod_{p\leq x}\left(1+\...
user147650
4 votes
0 answers
152 views
Consecutive integers which are products of Fibonacci numbers
Let $F_1, F_2, \dots$ be the sequence of Fibonacci numbers, and let $\mathcal{M}$ be the set of positive integers expressible as a product of Fibonacci numbers (OEIS A065108). One can prove that $$F_{...
- 141
2 votes
0 answers
153 views
Question regarding proof of Mertens' estimates in Montgomery-Vaughan's "Multiplicative number theory"
I have been trying to read Theorem 2.7 of Montgomery-Vaughan's "Multiplicative number theory" volume 1, and there is an issue I have run into: in the proof of subpart (e), when they write $$\...
- 81
4 votes
1 answer
312 views
Average of sums of $r_2(n^2+d^2)$
Let $r_2(n)$ denote the number of ways in which a positive integer $n$ is expressed as the sum of two squares (integers). I would like to know if there is a result that gives the exact behavior of (as ...
2 votes
2 answers
870 views
Convergence of Euler product and Dirichlet series in the same half-plane?
I'm crossposting this from math.stackexchange because I think it might be inappropriately research-level for the community over there. Suppose we have an Euler product over the primes $$F(s) = \prod_{...
- 263
8 votes
0 answers
369 views
Does every multiplicative function have a logarithmic average?
Is it true that for every completely multiplicative function $f:\mathbb N\to\mathbb C$ with $|f(n)|=1$ for all $n$, the logarithmic average $$\lim_{N\to\infty}\frac1{\log N}\sum_{n=1}^N\frac1nf(n)\...
- 1,896
12 votes
0 answers
294 views
Strong uniqueness of Euler's totient function
Let $f:\mathbb N\to \mathbb C$ be some arithmetical function. Define $\varphi_f(n)$ by the following formula: $$ \varphi_f(n)=\sum_{\substack{k\leq n \\ (k,n)=1}}f(k). $$ In other words, $\varphi_f(...
- 7,773
2 votes
0 answers
165 views
Well-known estimate for $L(s,\chi)$ for $\sigma=\text{Re}s\geq 1/2$
This is a very short question. Let $s=\sigma+it$ be a complex number with $\sigma \geq 1/2$. In the paper 'Jutila, Matti. "On the Mean Value of $L(1/2, \chi)$ FW Real Characters." Analysis 1.2 (...
- 663
2 votes
1 answer
196 views
Questions about a certain set of primes
Let $A$ be a set of prime numbers, generated by the following procedure. Let $A_0 = \{2\}$. Let $A_n$ be generated by setting $x_n = (\prod_{p_i \in A_{n-1}}p_i) + 1$, and adding all the prime factors ...
- 1,106
5 votes
1 answer
226 views
Uniformity in Wirsing's Mean Value Theorems
In two important papers of Wirsing, namely "Das asymptotische Verhalten von Summen über multiplikative Funktionen" (1961) and its follow up (1967), several results on mean values of multiplicative ...
- 15.5k
1 vote
0 answers
108 views
Existence of equation about the product of the divisor sum function
Let $\sigma_k(n)$ be the sum of the $k$-th powers of the positive divisors of $n$ and $\mu(n)$ be the Möbius function. As Arithmetic function - Wikipedia mentioned, there is an equation that $$\...
- 123
4 votes
0 answers
225 views
Math software / language for analytic / multiplicative number theory
What software/languages are the most used to do computations in analytic / multiplicative number theory? I use Python, Maple, etc., but each time I want to compute expressions like, for $n$ with an ...
- 607
1 vote
1 answer
381 views
Is it possible to find all integer functions which satisfy $f(m!+n!)\mid f(m!)+f(n!)$ and $m+n \mid f(m)+f(n)$?
I'm interesting to know more about multiplicative property of integer functions then I'd like to ask this humble question: Question: Is it possible to find all integer functions which satisfy $f(m!+...
- 11
6 votes
1 answer
359 views
A question about $(0,1]$-valued multiplicative functions
Suppose $f:\mathbb{N}\to [0,1]$ is a multiplicative function (i.e. $f(nm)=f(n)f(m)$ whenever $m$ and $n$ are coprime). Suppose $f$ has non-zero mean, which means $$ \lim_{N\to\infty}\frac{1}{N} \sum_{...
- 63
10 votes
0 answers
256 views
The multiplicative group generated by shifted primes
I am asking for references about the following problem. In particular, it is still open? If not, what is the state of the art result? Problem 1. Let $\Gamma$ be the multiplicative subgroup of $\...
user40023
1 vote
0 answers
91 views
All all hypo-multiplicative functions linear combinations of quasi-multiplicative functions?
A function is called quasi-multiplicative by many authors if $f(m)f(n)=f(1)f(mn)$, a slight generalization of multiplicativity. (Basically a multiplicative function times a constant is a quasi-...
- 9,379
16 votes
1 answer
2k views
Least prime in an arithmetic progression and the Selberg sieve
My question concerns a technical step in the proof of Linnik's theorem on the least prime in an arithmetic progression, as presented in Chapter 18 of Iwaniec-Kowalski: Analytic number theory. The ...
- 114k
6 votes
0 answers
362 views
Linear combination of multiplicative functions
Carlitz showed necessary and sufficient conditions for an arithmetic function to be a linear combination of two multiplicative functions. He mentions the possibility of generalizing to $k$ ...
- 9,379
1 vote
1 answer
372 views
Number of biquadrates mod n
Is there an explicit formula for the number of fourth powers mod n? Finch & Sebah [1] give theorems, partially folklore, for squares and cubes mod n, but I don't know of a similar formula for ...
- 9,379