Number of squareful integers less than x

  • Thread starter Boorglar
  • Start date
  • Tags
    Integers
In summary, the convolution method yields an asymptotic estimate for the number of squarefull integers ≤ x that is O(x^{\frac{1}{3}}). This estimate can be simplified using the Dirichlet series for µ(n) and (µ^2 * µ)(n).
  • #1
Boorglar
210
10
I'm doing the exercises from Introduction to Analytic Number Theory by A.J. Hildebrand (online pdf lecture notes) from Chapter 2: Arithmetic Functions II - Asymptotic Estimates, and some of them leave me stumped...

1. Homework Statement


Problem 2.14:
Obtain an asymptotic estimate with error term [itex]O(x^{\frac{1}{3}})[/itex] for the number of squarefull integers [itex] ≤ x [/itex], i.e., for the quantity [itex]S(x) = \left\{n ≤ x : p | n => p^{2} | n\right\} [/itex].

2. Homework Equations

The text describes a method known as the "convolution method" to evaluate sums of arithmetic functions asymptotically. In our case, the arithmetic function would be the characteristic function of the squarefull integers, a(n) = 1 if n is squarefull and 0 otherwise.

If [itex]a = f * g[/itex] (Dirichlet convolution), then [tex]\sum_{n ≤ x} a(n) = \sum_{d ≤ x} g(d) F\left(\frac{x}{d}\right)[/tex] where [itex]F(x)[/itex] is the summatory function of [itex]f[/itex].

The Attempt at a Solution


I am not even sure how to start. I tried expressing [itex]a(n) = 1 * (\mu * a)[/itex] thus using [itex]f = 1[/itex] and [itex]g = \mu * a[/itex]. But I can't find a way to estimate the sum [tex]\sum_{d ≤ x} g(d) \left\lfloor{\frac{x}{d}}\right\rfloor[/tex] Here [itex]\mu[/itex] means the Mobius function.
 
Physics news on Phys.org
  • #2
Maybe it would be a good idea to investigate S(x) for different values of x. You could plot the number of squarefull integers for x up to some cutoff, for example. It couldn't hurt! Maybe it will reveal some pattern that will give you an idea of how to solve the problem.
 
  • #3
So I finally solved the problem, in a totally different (and way simpler) method -_-

I used an earlier result from another problem, saying that squarefull integers can be written uniquely in the form [itex]a^2b^3[/itex].
So to count the squarefull integers [itex]\leq x[/itex] you can just do [tex]\sum_{a^2b^3 \leq x} 1 = \sum_{b \leq x^{1/3}} \left\lfloor{\frac{\sqrt x}{b^{3/2}}}\right\rfloor[/tex] which eventually simplifies to [tex]\zeta(3/2)\sqrt x + O(x^{1/3})[/tex]

UPDATE:
Ah, turns out I was wrong... The representation [itex]a^2b^3[/itex] is not unique. For example, [itex]p^8 = (p^4)^2 * 1^3 = p^2 * (p^2)^3[/itex]. I think we need the additional condition that [itex]b[/itex] is squarefree...
So the sum is actually [tex]\sum_{a^2b^3 \leq x} µ^2(b) = \sum_{b \leq x^{1/3}}µ^2(b) \sum_{a \leq \frac{x^{1/2}}{b^{3/2}}}1 = \sqrt x \sum_{b \leq x^{1/3}}\frac{µ^2(b)}{b^{3/2}} + O(x^{1/3})[/tex]

which still becomes something of the form [itex] C \sqrt x + O(x^{1/3}) [/itex] but [itex] C = \sum_{b = 1}^{\infty} \frac{µ^2(b)}{b^{3/2}}[/itex] which I can't really simplify...

After playing with this expression and using Dirichlet series of [itex]µ(n)[/itex] and [itex](µ^2 * µ)(n)[/itex], I found that [itex]C = \frac{\zeta(3/2)}{\zeta(3)} [/itex].
 
Last edited:
  • Like
Likes Geofleur

1. What are squareful integers?

Squareful integers are numbers that are the product of two or more distinct perfect squares. For example, 12 is a squareful integer because it can be expressed as 2^2 * 3, while 15 is not a squareful integer because it cannot be expressed as the product of distinct perfect squares.

2. Why is the number of squareful integers less than x important?

This number is important in a variety of mathematical problems and applications. For example, it can be used in number theory to study the distribution of primes, or in combinatorics to count the number of possible combinations of squareful integers. It can also be used to solve problems in cryptography and coding theory.

3. How is the number of squareful integers less than x calculated?

The number of squareful integers less than x can be calculated using various mathematical techniques, such as sieving or generating functions. It also involves considering the prime factorization of x and counting the number of ways it can be expressed as the product of distinct perfect squares.

4. Is there a closed-form formula for the number of squareful integers less than x?

No, there is no known closed-form formula for this number. However, there are various asymptotic estimates and bounds that can be used to approximate it.

5. What are some real-life applications of the number of squareful integers less than x?

One example is in the field of cryptography, where the number of squareful integers less than x can be used to generate secure public and private keys. It can also be used in coding theory to construct optimal codes for data storage and transmission. Additionally, it has applications in computer science and engineering, such as in the design of error-correcting codes for communication systems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
559
  • Calculus and Beyond Homework Help
Replies
4
Views
604
  • Calculus and Beyond Homework Help
Replies
3
Views
356
  • Calculus and Beyond Homework Help
Replies
14
Views
429
  • Calculus and Beyond Homework Help
Replies
2
Views
62
Replies
23
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
444
  • Calculus and Beyond Homework Help
Replies
3
Views
515
  • Calculus and Beyond Homework Help
Replies
2
Views
870
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top