1
$\begingroup$

Let $n$ be a positive integer, and consider the set $\{1, \dots, n\}$. If we remove from this set all the numbers $a$ which satisfy $$ a \equiv 0 \mod d $$ for at least one divisor $d$ of $n$ (where we only consider $d \neq 1$, of course), then it is well-known that the total number of remaining elements is given by the Euler totient function $\varphi(n)$. This is quite easy to show - note that it uses the fact that actually it is sufficient to consider those divisors $d$ which are primes, since then all composite divisors are incorporated automatically.

Now here is my problem. Let $\gamma \in [0,1]$ be a fixed real number. For a real number $y$, let $[y]$ denote the integer which is closest to $y$. From the set $\{1, \dots, n\}$ I have to remove all the elements $a$ for which $$ a \equiv [\gamma d] \mod d $$ for at least one divisor $d$ of $n$ (where again we only consider $d \neq 1$). How many elements remain? In contrast to the case $\gamma=0$, now it obviously is not sufficient anymore to consider only prime divisors $d$. A trivial lower bound for the number of remaining elements is $$ n - \sum_{d | n, ~d \neq 1} \frac{n}{d} = n - \sum_{d | n, ~d \neq n} d, $$ since for every divisor $d$ we remove at most one residue class (which contains $n/d$ elements).

Question: Is there any significantly better lower bound for the number of remaining elements? (Note that I do not want to assume anything whatsoever on $n$ or $\gamma$.)

$\endgroup$
  • 1
    $\begingroup$ Do you know about the Jacobsthal function? The techniques used to examine that function might well serve you here. $\endgroup$ – Greg Martin Jun 26 '18 at 21:03
  • $\begingroup$ Have you tried this for abundant n? It seems to me that you could get the number of remaining elements close to zero for a good choice of lambda. Greg Martin's suggestion of looking at Jacobsthal's function is interesting, and suggests to me Lehmer's 1951 paper on the distribution of totatives (link found elsewhere on MathOverflow). Gerhard "Maybe Make Lambda Really Small" Paseman, 2018.06.26. $\endgroup$ – Gerhard Paseman Jun 27 '18 at 5:18
2
$\begingroup$

Let $D=\{ d>1\ :\ d\mid n \}$ be the set of nontrivial divisors of $n$. Then by inclusion-exclusion, the number of elements remaining after sieving based on $a\equiv 0\pmod{d}$ equals $$\sum_{S\subseteq D} (-1)^{|S|}\frac{n}{\mathrm{lcm}(S)},$$ where $\mathrm{lcm}(S)$ is the least common multiple of the elements of set $S$ with $\mathrm{lcm}(\emptyset):=1$. Here $\frac{n}{\mathrm{lcm}(S)}$ is the number of solutions from $\{1,2,\dots,n\}$ to the system of congruences $\{ x\equiv 0\pmod{d}\ :\ d\in S\}$. One can easily see that this system is always soluble and equivalent to a single congruence $x\equiv 0\pmod{\mathrm{lcm}(S)}$. It is an exercise to show that the above sum equals $\varphi(n)$.

Similar formula holds when the sieving is done based on $a\equiv [\gamma d]\pmod{d}$. The number of remaining elements in this case equals $$R := \sum_{S\subseteq D} (-1)^{|S|} N_S,$$ where $N_S$ is the number of solutions from $\{1,2,\dots,n\}$ to the system of congruences $\{ x\equiv [\gamma d]\pmod{d}\ :\ d\in S\}$. If such system is soluble, we again have $N_S=\frac{n}{\mathrm{lcm}(S)}$; otherwise $N_S=0$. So, to evaluate $R$ one needs to identify the subsets $S$ corresponding to soluble systems.

A system $\{ x\equiv [\gamma d]\pmod{d}\ :\ d\in S\}$ is soluble iff every pair of congruences in it is consistent, i.e., iff for every $d_1,d_2\in S$, $\gcd(d_1,d_2)\mid ([\gamma d_1] - [\gamma d_2])$.

Let us consider the graph $G$ on the vertices being elements of $D$, where vertices $d_1,d_2\in D$ are connected with an edge whenever $\gcd(d_1,d_2)\mid ([\gamma d_1] - [\gamma d_2])$. Then $$R = \sum_{C} (-1)^{|C|}\frac{n}{\mathrm{lcm}(C)},$$ where the sum is taken over all cliques $C$ in $G$.

Using the result about $\varphi(n)$, the last sum can further be reduced to just maximal cliques in $G$. Namely, let $\mathfrak{C}$ be the set of all maximal cliques in $G$. Then $$R = \sum_{\emptyset\ne J\subseteq \mathfrak{C}} (-1)^{|J|-1} \frac{n}{\mathrm{lcm}(\cap_J)}\cdot\varphi(\mathrm{lcm}(\cap_J)),$$ where $\cap_J := \bigcap_{C\in J} C$.

$\endgroup$
  • $\begingroup$ Thank you - but does that give any (simply) estimates on the number of remaining elements? In the case of $\gamma=0$ things are controlled by the Euler totient function, and the number of remaining elements is essentially between $n/\log \log n$ and $n$. How small can the number of remaining elements become for other $\gamma$? $\endgroup$ – Kurisuto Asutora Jun 28 '18 at 6:28
  • 1
    $\begingroup$ This shows that the number of remaining elements is related to the connectivity of graph $G$. First, as the number of vertices is $|D|$, it is easy to get exact when $n$ has small number of divisors (e.g., when it's semiprime). Second, one can expect that for irrational $\gamma$, $G$ would be rather sparse, giving a small number of terms in the last formula for $R$. On the other hand, when $\gamma=0$, the graph $G$ is complete, giving just a single term in the formula (as $|\mathfrak{C}|=1$). So, it's all really about the structure of $G$. $\endgroup$ – Max Alekseyev Jun 28 '18 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.