For the problem I am working on I have realised that some of the proofs could be slightly simplified if a certain number theoretic question has a positive solution. Now, the problem is in finite group theory, and unless the answer is really "immediate" I don't think that I intend to use number theoretic techniques. Nevertheless I am intrigued by the question and I would love to know the answer. Here it is.

Consider the set $X$ of natural numbers $n$ relatively prime to their Euler totien function $\varphi(n)$. It is important (I believe) to observe that, given $n\in\mathbb{N}$, the size of $\{x\in X\mid x\leq n\}$ is asymptotic to $an/\log\log\log n$ (for some absolute constant $a$).

Let $Y$ be a subset of $X$ containing all prime numbers. Suppose that, given $n$, the size of $\{y\in Y\mid y\leq n\}$ is asymptotic to $bn/\log n$ (for some absolute constant $b$). This is the whole information I have for $Y$.

Consider $Z$ the subset of $X$ consisting of all the elements $x\in X$ such that, for every divisor $m$ of $x$ with $m$ not being a prime, we have $m\notin Y$.

I am interested in the growth of the size of $\{z\in Z\mid z\leq n\}$. Does it grow as $n/\log\log\log n$ or less?

  • $\begingroup$ Isn't $Z$ just equal to $X$? By definition, the elements of $Y$ are prime numbers, and so $m$ not being prime forces $m \not\in Y$. $\endgroup$ – Jeremy Rouse Jul 17 '15 at 12:33
  • $\begingroup$ @JeremyRouse: I read the condition as “$Y$ be a subset of $X$ containing all prime numbers, and possibly some other numbers”. $\endgroup$ – Emil Jeřábek Jul 17 '15 at 13:08
  • $\begingroup$ Yes, I have very little information on $Y$. I know that $Y$ is contained in $X$ and that it contains all prime numbers. Moreover I know that $Y$ is quite "small" compared to $X$. So, I am hoping that this will force $Z$ to be as "big" as $X$. (Answering to the clarification above: $Y$ can contain non prime numbers.) $\endgroup$ – Pablo Spiga Jul 17 '15 at 16:23
  • $\begingroup$ It might clarify things to note that this is "happening inside S", where S is the set of squarefree numbers and has a natural semilattice structure on it. Z is just X intersect the complement of a join-ideal of S generated by those members of Y that are not primes. If there are finitely many nonprime members of Y, it may be straightforward to show the ideal grows slowly. It may also be possible to find a "sparse infinite cover" which would force Z to be much smaller than you hope. Gerhard "This Mindset Worked Once Before" Paseman, 2015.07.17 $\endgroup$ – Gerhard Paseman Jul 17 '15 at 19:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.