Welcome to MathOverflow

Question

10

1

Let $X$ denote the largest subset of odd integers with the property that every exponent in the prime factorization of any $x \in X$ belongs to $X$.

The conjecture states that the density of $X$ among the integers is $1-\frac{1}{\sqrt{3}}$.

Is this conjecture correct ?

edited Feb 13 2012 at 20:50

asked Feb 13 2012 at 17:53

Edinah
113●5

1

Do you have any evidence, or a citation, for this conjecture? At first glance, it seems very unlikely to me that this density would have a simple formula, but that's just a first glance. – David Speyer Feb 13 2012 at 19:34

I have only experimental evidence for the conjecture. I wrote up a sage program to verify the conjecture for integers up to 20 billon and recovered the probability up to 7 digit of precision. – Edinah Feb 13 2012 at 20:48

I updated my original response. The new response shows that any $X$ has density at most 0.4226496 which is smaller than $1-1/\sqrt{3}$. – GH Feb 13 2012 at 21:20

@Edinah: I responded to your criticism below (as a comment to my response). – GH Mar 24 2012 at 7:59

GH · Accepted Answer · 2012-02-13 21:48:20Z UTC

13

This is an update of my original response which was incorrect.

The conjecture is false. I will show that any $X$ in the conjecture has density at most

$$ 0.4226496 < 1-\frac{1}{\sqrt{3}}= 0.4226497...$$

Let $Y$ be the set of odd numbers whose prime exponents are odd and different from $9$. Clearly, any $X$ in the conjecture is a subset of $Y$. Yet, the density of $Y$ equals

$$ \frac{1}{2}\prod_{p>2}\left(1-\frac{1}{p}\right)\left(1+\frac{1}{p-p^{-1}}-\frac{1}{p^9}\right) $$

which is less than

$$ 0.42264954363092750400907132916 $$

by the SAGE command

(1/2)*prod([RealField(100)(1-1/p)*(1+1/(p-1/p)-1/p^9) for p in prime_range(3,1000000)])

edited Feb 13 2012 at 21:48

answered Feb 13 2012 at 20:11

GH
15.7k●1●34●57

	Dear GH, Thank you very much for your comment. It took me while to get back to you because I wanted to carefully check everything, I beg to differ. I ran the sage code w can be found at the link www.cs.rutgers.edu/~gnang/sage_code/ The output of the computation can be found in output.txt file and got the density estimate to be for number in the range (1,2^28) to be equal to (1-0.577350318431854)=0.422649681568146 > 0.42264954363092750400907132916 (your estimated upper-bound). I think the issue lies in the fact the estimate fails to account for the recursive nature of the set X. Best, – Edinah Mar 24 2012 at 1:51
	@Edinah: To contradict me you also need to prove that by extending your range $(1,2^{28})$ to all positive integers, your density stays above my claimed upper bound. You cannot prove this simply because my proof is correct. You see, I constructed a set $Y$ which provably contains any $X$, and whose density is provably less than your conjectured $1-1/\sqrt 3$. The density of $Y$ is given by an infinite product over primes with factors in $(0,1)$, so an upper bound for it is given by any finite subproduct. SAGE can calculate the finite product with great precision and falsifies your conjecture. – GH Mar 24 2012 at 7:56
	@GH, I am currently working with Edinah to write a paper on this problem. I was not aware of the fact that this question was posted on this site, and I have independently come to the same conclusions as you have (albeit with a slightly different formula). The conclusions of the paper were all found independently from yours, but we wouldn't want to publish something without first asking if you would like us to acknowledge your disproof (i.e., this post). If you would like to be acknowledged, how so? – Pat Devlin May 9 2012 at 18:07
	@Pat: Thank you. I would like to respond by email. What is your address? – GH May 10 2012 at 13:00
	@Pat: Mail sent. – GH May 10 2012 at 16:38

Greg Martin · Answer 2 · 2012-02-13 20:23:32Z UTC

Let $A$ be any set of positive integers such that $1\in A$, and let $B$ be the set of integers such that every exponent in the prime factorization of any $x\in B$ belongs to $A$. Then the density of $B$ exists and equals $$ \prod_{\text{primes }p} \bigg( 1-\frac1p \bigg) \bigg( 1 + \sum_{a\in A} \frac1{p^a} \bigg). $$ In this case, $A=B=X$ (which is kind of cool).

A Conjecture on the Density of a subset of integers

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.