Timeline for Structure of set with large pairwise gcd's
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 25, 2019 at 14:48 | comment | added | Gerhard Paseman | In graph theoretic terms, the argument does apply to the largest clique with common gcd, and as in alpoge's suggestion, it matters how many large cliques make up your set. I believe thinking about 3-smooth or 5-smooth numbers containing your set S is a good way to approach this problem. Gerhard "Maybe Small Divisors Will Coalesce" Paseman, 2019.05.25. | |
| May 25, 2019 at 10:49 | comment | added | alpoge | @KurisutoAsutora I see —- I was just going off your parenthetical that perhaps there is a small set of factors for which every element is a multiple of one of these factors. In any case I certainly agree that the optimal bound should be far better, I just gave a quick answer in case the minimum of d(m) over your set was a good enough bound for you. | |
| May 25, 2019 at 10:47 | comment | added | Kurisuto Asutora | @alpoge: As I understand, this isn't really a decomposition, since the $S_d$ are not dijoint, right? Also, having $N^\varepsilon$ "substructures" is too much for me, I thought it should rather be something like constant or logarithmic or something. | |
| May 25, 2019 at 10:45 | comment | added | Kurisuto Asutora | @user44191: I am thinking of $m_1, ..., m_M$ of being roughly of the same size, so let's say they are all in $[N,2N]$. I didn't mean that they all have to be extremely close to $N$. | |
| May 25, 2019 at 10:44 | comment | added | Kurisuto Asutora | Thank you all for the answers. @Gerhard: It's a correct observation. However, as I understand this really only applied when ALL $M^2$ pairwise gcd's are that large. If I can only assume that, say, $M^2/10$ pairwise gcd's are that large, then such an argument doesn't really apply anymore, right? | |
| May 24, 2019 at 23:39 | comment | added | alpoge | I’m gonna be lazy and note the following. Let’s write S instead of \mathcal{M} since I’m on my phone. Let m\in S. There are << N^\eps divisors of m. In particular there are << N^\eps divisors of m that are of size \sqrt{N}. For each such divisor d | m of size \sqrt{N}, let S_d := {n\in S : d | n}. Observe that the union of the S_d is all of S by hypothesis. Observe also that every S_d is of the “trivial” form. Thus there is a decomposition of S into a union of few “trivial” subsets. I hope I get to learn a weighted Erdos-Ko-Rado theorem in the inevitable “correct” answer to this question! | |
| May 24, 2019 at 22:33 | comment | added | user44191 | Do you have any specific bounds? For example, how small is $m_1$ allowed to be in terms of $N$, or how large is $m_M$ allowed to be? | |
| May 24, 2019 at 14:53 | comment | added | Gerhard Paseman | You can't have any small differences, second differences, third differences, etc. So yes, that is what they look like: multiples of the same gcd. For high proportion, do 3-smooth numbers satisfy? Gerhard "You're Not Just Talking Smooth" Paseman, 2019.05.24. | |
| May 24, 2019 at 8:00 | history | asked | Kurisuto Asutora | CC BY-SA 4.0 |