Timeline for Is the number of solutions of $\phi(x)=n!$ bounded? If yes, what is its bound?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 9, 2020 at 16:53 | comment | added | Emil Jeřábek | @MaxAlekseyev It’s easy to give a simple self-contained argument for bounds much closer to optimal. See my answer. | |
| Jul 8, 2020 at 18:44 | comment | added | Max Alekseyev | @GerhardPaseman: The product here is taken over all $d=p-1\mid m$ for candidate primes $p$ (and possibly some composites), where the product terms are the upper bound for the number of possible exponents. I believe you think more of the bound ala A045778(m), which needs to account for existence of multiple primepower preimages of the same number. My approach is free from this issue. | |
| Jul 8, 2020 at 17:06 | comment | added | Max Alekseyev | @EmilJeřábek: Of course, it's an overkill. My goal was to give a simple self-contained argument for bounding the number of solutions. | |
| Jul 8, 2020 at 13:17 | comment | added | Emil Jeřábek | The bound is certainly overkill. First, it is well known that $n/\varphi(n)=O(\log\log n)$, whence $\varphi(n)\le m\implies n=O(m\log\log m)$. Even better, Wikipedia cites a result that $|\{n:\varphi(n)\le m\}|=O(m)$. In fact, the expression given there implies $|\{n:\varphi(n)=m\}|=O\bigl(m(\log m)^{-k}\bigr)$ for all constant $k$. | |
| Jul 8, 2020 at 9:34 | vote | accept | zeraoulia rafik | ||
| Jul 8, 2020 at 3:45 | comment | added | Gerhard Paseman | I am completely misreading your formula. I factor m into components each of the form (p^{k-1})(p-1) and call that component d, and think that each term counts the number of possible p that give rise to the same d. Until I figure this out, assume we are talking at cross purposes for now. Gerhard "Needs Some More Head Scratching" Paseman, 2020.07.07. | |
| Jul 8, 2020 at 3:32 | comment | added | Max Alekseyev | @GerhardPaseman: In your example for $m=18$, $27=3^3$ corresponds to $d=2$ (and exponent 3 from its exponent range), $19$ corresponds to $d=18$. I'm not sure what you mean under "replaced by". | |
| Jul 8, 2020 at 3:26 | comment | added | Gerhard Paseman | But phi (27)=phi(19). How does your enumeration account for cases where 27 "is replaced by " 19 as factors of a potential solution a? Gerhard "One Divisor Unequals One Prime" Paseman, 2020.07.07. | |
| Jul 8, 2020 at 3:19 | comment | added | Max Alekseyev | @GerhardPaseman: One divisor cannot correspond to different $p$, since $d$ in my answer essentially stands for $p-1$ (and different divisors give different $p$'s). I did not attempt to make the bound as small as possible -- that's a separate question. | |
| Jul 8, 2020 at 3:01 | comment | added | Gerhard Paseman | I think you also have to worry about one divisor of m corresponding to two different primes p. Gerhard "Maybe Leave Exponent At M" Paseman, 2020.07.07. | |
| Jul 8, 2020 at 2:53 | comment | added | Gerhard Paseman | Indeed. However you can replace the exponent with 2sqrt(m) , and if you look at divisor pairs, you can make the base smaller also. Gerhard "Likes To Improve Through Simplification" Paseman, 2020.07.07. | |
| Jul 8, 2020 at 2:35 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
deleted 17 characters in body
|
| Jul 8, 2020 at 2:32 | comment | added | Max Alekseyev | @GerhardPaseman: Nice catch! That was the price of blindly copying bounds from Wikipedia (it seems that $\exp(x/2)$ factor is lost in the bounds for $\mathrm{Ei}(x)$ there). Anyway, this approach was somewhat overengineered, and I've replaced it with a simpler one. | |
| Jul 8, 2020 at 2:30 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
deleted 604 characters in body
|
| Jul 8, 2020 at 2:13 | comment | added | Gerhard Paseman | I don't understand the upper bound on E. The integral from 2 to m is lower bounded by m/log m. Even if you don't do the integration but estimate the sum over divisors, I am not seeing your power of log as an upper bound. Gerhard "Am I Adding This Wrong?" Paseman, 2020.07.07. | |
| Jul 7, 2020 at 22:53 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
typo
|
| Jul 7, 2020 at 20:52 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
missing factor added
|
| Jul 7, 2020 at 19:52 | history | answered | Max Alekseyev | CC BY-SA 4.0 |