3
$\begingroup$

For a given $n > 0$ Landau's function is defined as $$g(n) := \max\{ \operatorname{lcm}(n_1, \ldots, n_k) \mid n = n_1 + \ldots + n_k \mbox{ for some $k$}\},$$ the least common multiple of all partitions of $n$. It is the maximal order of an element in the symmetric group $S_n$.

But is there anything known if we restrict the number of summands, i.e. define $$ g(n, k) := \max\{ \operatorname{lcm}(n_1, \ldots, n_k) \mid n = n_1 + \ldots + n_k \}, $$ Surely $g(n,1) = n$ and $g(n) = \max\{g(n,1), g(n,2), \ldots, g(n,n)\}$ and $g(n,k) = 0$ if $k > n$. Is there a recursive relation. Do you know any references where this generalization is studied?

$\endgroup$
  • $\begingroup$ It will be roughly approximated by (n/k)^k for small k ( maybe even up to k about sqrt(n/log n). For large k it will be much smaller. Gerhard "Do You Need Large K?" Paseman, 2018.11.02. $\endgroup$ – Gerhard Paseman Nov 2 '18 at 20:56
  • $\begingroup$ @GerhardPaseman Thanks, I am more interested in small values of $k$. And I would be glad if you can give arguments or derivations for your claims!? $\endgroup$ – StefanH Nov 2 '18 at 21:44
  • $\begingroup$ The basic idea is to start with k primes whose average is near n/k, and then tighten it up by replacing the further terms with coprime smooth numbers near n/k. I don't know of references for this specific problem, but my work with Jacobsthal's function tells me this is a quick route to the result for small k. At some point one has to transition to coprime powers, and I am unclear as to where that transition begins. Gerhard "May Need Pencil And Paper" Paseman, 2018.11.02. $\endgroup$ – Gerhard Paseman Nov 2 '18 at 21:50
  • $\begingroup$ @GerhardPaseman Okay, I am really a beginner at number theory, the term "smooth number" makes no sense to me, and I am not exactly sure what you mean with coprime power. But if it is too simple for you to write it down, maybe you can give more precise references where similar techniques are applied... $\endgroup$ – StefanH Nov 2 '18 at 21:55
  • $\begingroup$ I'll post a response soon. Smooth numbers are composite numbers with only small prime factors, and I want to choose a set of coprime numbers , some of which are powers of a prime, to maximize the LCM. If no one else has a good answer, I'll post an expansion of these ideas. Gerhard "Meanwhile, I Will Advertise 37679" Paseman, 2018.11.02. $\endgroup$ – Gerhard Paseman Nov 2 '18 at 22:04
1
$\begingroup$

Let $\mu=\frac{n}k.$ Then we certainly can't do as well as $\mu^k.$ Taking into account that the parts are integers of which all or all but one are odd reduces the upper bound to $\mu^k+c\mu^{k-2}$ for $c $ around $\frac{k^3}3.$ And that does not take into account that at most one part is $0 \bmod 3$ or $0 \bmod 5.$ However I suspect that for fixed $k$ one can get an upper bound of the form $\mu^k+c_k\mu^{k-2}$ by considering only primes up to $k.$ That is to say that there is an $N_k$ so that the solution depends on the congruence class of $n \bmod N.$ Perhaps good bounds can be given without going through all the cases.

Suppose $n=km+r.$

For $k=2$ use $m,m+1$ for odd $n=2m+1$ and $m-1,m+1$ or $m-2,m+2$ for $n=2m.$

For $k=3$ and $-1 \leq r \leq 1,$

  • when $r=0,$ use $m-1,m,m+1$ or $m-2,m,m+2$

  • when $r=\pm 1$ try $m-3r,m+r,m+3r$ or $m-r,m,m+2r$ depending if $m$ is even or odd. The only possible problem is if the top and bottom numbers are multiples of $3.$ In those cases use $m-3r,m-r,m+5r$ or $m-3r,m,m+4r.$

It is not obvious to me what happens next. Here is a start at the case $k=5.$ Consider the congruence class of $n \bmod 30$ or in a few cases $\bmod 90$ or $\bmod 150.$

  • consider $6k-3,6k-1,6k,6k+1,6k+3.$ The $\gcd$ of any two of these divides $12$ so it suffices to note that , for $k$ not a multiple of $3$ only one of these is even and only one is a multiple of $3.$ This takes care of $n=30k$ unless $k=3j.$ In that case $6k-5,6k-2,6k-1,6k+1,6k+7$ works for $\mu^5-60\mu^3$

  • $6k\pm 13,6k \pm 7,6k \pm 1,6k \mp 5,6k \mp 11$ always works for $30k \pm 5.$ That might never be the optimal solution.

So that is $3$ of the $30$ congruence classes mod $30.$ A similar analysis for the other $27$ cases might yield a result without any consideration of primes greater than $5.$

$\endgroup$
  • 1
    $\begingroup$ For k=2 I think you want something different. For odd n=2m+1 choose m and m+1. For even n=2m, m and m-1 always work although sometimes m+1 and m-1 work. The general problem is of interest and relates to Jacobsthal's function, but is even more challenging. Gerhard "Is Challenging His Thought Processes" Paseman, 2018.11.03. $\endgroup$ – Gerhard Paseman Nov 4 '18 at 1:54
  • $\begingroup$ @GerhardPaseman OK, corrected. Maybe I'll look at some cases to better understand this. $\endgroup$ – Aaron Meyerowitz Nov 4 '18 at 5:52
  • $\begingroup$ For what should I use those $m$'s?? Could you please be more specific about that... $\endgroup$ – StefanH Nov 4 '18 at 20:13
  • $\begingroup$ Are you interested in a particular $k$? For $k=3$ and $n=1801$ one has$m-3r,m-r,m+5r=597,599,605$ in general , for $n=18j+1$ one can always use $6j-3,6j-1,6j+5$ that gives roughly $\mu^3-17\mu$ for $\mu=n/3.$ $\endgroup$ – Aaron Meyerowitz Nov 4 '18 at 21:30
  • $\begingroup$ I suspect one can find k coprimes in every interval of length at most h(k+1) with h(k) being Jacobsthal's function g(P_k) in which case $ g(n,k)$ approaches $(n/k)^k$ quickly for fixed k and n not much larger than, say h(k)^2. Computer trials support the estimate of h(k+1), and I am trying to prove it. Gerhard "I Think This Looks Familiar" Paseman, 2018.11.06. $\endgroup$ – Gerhard Paseman Nov 6 '18 at 20:30
1
$\begingroup$

Edit 2018.12.06

I have not yet found an explicit result regarding sets of coprimes In an interval. Erdos and Sarkozy in a 1993 article On sets of coprime integers in intervals establish several results which confirm the qualitative result, that for every $k$ there is an interval length $d(k)$ (their Theorem 7 uses $n$ where I use $d$) which guarantees at least $k$ coprimes in any interval of length $d(k)$. However, the error terms they use suggest $d(k) \gt 2^k$, whereas I am confident one can bring $d(k)$ down to near Jacobsthal's $C(k)$. So I claim that asymptotically, $g(n,k) \in \Theta((n/k)^k)$, and that it remains to show that for each $k$ and for all $n$ greater than (say) $k^5$, $2*g(n,k) \gt (n/k)^k$.

End Edit 2018.12.06.

Edit 2018.11.24

The post below is too long. The short version is that the claim that $g(n,k)$ is like $(n/k )^k$ does hold for fixed $k$ and sufficiently large $n$, primarily because there is an interval of length $d$ ($d$ not depending on $n$) which contains $n/k$ and $k$ mutually coprime numbers summing to at most $n$. The post will be updated later with details. The main change is to pick numbers $m$ from the interval In order of decreasing $L(m)$, and the details are to show you can do this to get $k$ coprimes, which I will post later.

End Edit 2018.11.24.

This question is taking me down an old path with a new perspective. I will relate the perspective to the problem, and then share the perspective.

The (perspective is motivated by a goal, and the) goal is to show there are $k$ numbers near $n/k$ which are mutually coprime, and really to show that 'near' is independent of $n$. For small values of $k$, it is easy to show this independence: for values of $k=1$ through $6$: (and larger) one has at least $k+1$ coprimes (my abbreviation for numbers which are pairwise coprime) in any interval of length $g(P_k)$. So to solve the version of the problem where you pick $k$ coprimes which sum to at most $n$, and $k$ is small, there is guaranteed a rather tight grouping in an interval around $n/k$, although $n/k$ may need to be slightly above the average to keep the sum from exceeding $n$.

(One way to show independence of $n$ is to consider an alternative problem: Fix $d$, and count coprimes in each interval of length $d$. The minimum value $M_d$ of the maximum sized subset of coprimes in an interval of length $d$ exists, does not decrease as $d$ grows, and this minimum value repeats with a period dividing the product of all primes at most $d$. To show that $M_d$ eventually exceeds $k$ is possible, but a simple argument requires $d$ being superexponential in $k$. However, in general I do not know what $M_d$ is given $d$.)

The problem where the sum of these $k$ coprimes is exactly $n$ is more challenging. If we extend the interval slightly, we may replace some coprimes with numbers which bring the sum to exactly $n$ (and still have these numbers mutually coprime to the other members). Although I believe this interval length will also be independent of $n$, I do not have an idea of how to prove such independence. (Actually, one idea is to bump up $d$ to get a set of $k+j$ coprimes in the interval and show that there are enough subsets of size $k$ to guarantee a sum of $n$, but I am seriously unclear as to the size of $j$.) Even so, there are enough primes that having one or two members a distance of, say, $O((\log n)^2)$ away from $n/k$ will still keep $g(n,k)$, the generalization of Landau's function, comfortably close to $(n/k)^k$. Incidentally, by showing this product is at least half of $(n/k)^k$, one confirms that a solution to the general problem (with $k$ small with respect to $n$) involves such a set of coprimes.

So what is the plan? To start, pick an interval of length $d$ containing $n/k$. If we find this choice does not work, we may increase $d$ and extend the interval in one or in both directions. For each integer $m$ in the interval, record $L(m)$, the least prime factor dividing $m$. (We assume $n$ comfortably large, say $n/k \gt k^2$. For smaller $n$ we may as well look at Landau's function directly.)

$L(m)$ is 2 for about half the numbers $m$ in the interval. If $d=P_j$, the product of the first $j$ primes, then for $0 \lt i \lt j$ we have $p_{i+1}$ appear about $\phi(P_i)/(P_i p_{i+1})$ fraction many times as a value for $L(m)$ in this interval. Asymptotically this is like $O(1/(p_i\log i))$. Indeed, this fraction is a good approximation for a few larger $i$ as well, but variations in the distribution of numbers with large $L(m)$ values in an interval appear, and one cannot rely on this estimate for $i$ that much larger. (I would not trust it for $i \gt j + j^{\epsilon}$.). One thing we can rely on: if $L(m)$ assumes $k$ distinct values in this interval, then there are at most $k$ coprimes in this interval. This is because any set of coprimes far away from 0 must have distinct values for $L(m)$. And for small values of $k$, one can show that there are exactly $k$ coprimes, and for values of $d$ not much larger than $k$ (certainly $d \leq k^2$ for small $k$).

It is tempting to conjecture that if there are $k$ many distinct $L(m)$ values in an interval of length $d$ far away from zero, there will be $k$ coprimes in that interval. However, I think it is possible for large $k$ to have the following situation: pick $k-1$ odd coprimes, and find that every even number has a factor in common with one of the odd coprimes. If this does happen, $k$ will have to be larger than 10, possibly larger than 24, so we will not see small counterexamples of this form.

Anyway, to handle this bit of ignorance, we increase $d$. We expand it so that when we collect more values of $L(m)$, we collect enough (maybe $2k$ many?) so that we pick the numbers with the $k$ largest distinct $L(m)$ values, and hope these numbers are mutually coprime.

Things look promising. For if we have $r$ and $s$ odd numbers with distinct $L$ values, if they have a common prime factor $p$, then $2p \lt d$, and so both $L$ values must be less than $d/2$. So if we get $k$ numbers with distinct $L$ values $d/2$ or larger, then we are guaranteed a coprime set. Unfortunately, there are cases where we are not guaranteed any $L$ values greater than $d/2$. (An easy example with at most 2 such $L$ values greater than $d/2$ is an interval centered around 0, or centered around the product of all the primes at most $d/2$.).

This post is getting too long. I will hand wave in this paragraph. So pick $d$ larger than the $k$th prime as follows: we look for primes greater than some prime $q$ so that there are at least $k$ of them and the sum of the reciprocals of these primes is at most 1/2. We ignore numbers with $L$ values $q$ or less. We have picked $d$ so that there are plenty of numbers left (say $k(log k)^2$ many). Now pick a number with the smallest $L$ value $p$ which is greater than $q$ as one of the coprime. This removes about $1/p$ of the remaining numbers from consideration, but let us pretend it removes $2/p$ fraction of these numbers. Now pick the next number with smallest remaining $L$ value for the next coprime, and eliminate from consideration all other numbers with that prime factor. Because $q$ is large enough, we can repeat this up to $k$ times before running out of numbers. There is more work to do, and this gives a weak bound, but it shows that $d$ exists for a given $k$ with $M_d$ at least $k$. I will add more to give an asymptotic for $d$ in terms of $k$, which will achieve the goal in a qualitative sense.

Gerhard "Let's Make This Turkey Fly!" Paseman, 2018.11.23

$\endgroup$
0
$\begingroup$

Before we address the issue of coprimality, let us mention maximizing and approximating the product of $k$ distinct positive integers whose sum is $n$. Simple methods show that $(n/k)^k$ is an upper bound on this product, and an achievable lower bound for distinct integers is $((n/k)^2 - (k/2)^2)^{\lfloor k/2 \rfloor }d$, where $d$ is 1 if $k$ is even, and $d$ is near $n/k$ otherwise (and $k$ big enough, say $k$ bigger than 5). When $k^5$ is small compared to $n^2$, this differs from the upper bound by a multiplicative factor of less than 2.

Of course, for $k$ larger than 3 we don't have $k$ consecutive positive integers being mutually coprime. In many cases though, we can find $k$ primes near $n/k$ in an interval of length $kd$ (where the nature of $d$ is interesting, but a lot of the time $d$ is close to $\log(n/k)$, and if we have $(d^2k^5)$ small with respect to $n^2$, we can stay within a factor of 2 of the upper bound. (Notice we are sacrificing the possibility that the primes sum to precisely n. For the rest of this post, we will relax this condition and require that the sum be at most n.) However, we now want to shift to finding $k$ coprimes .

To avoid worrying about picking a subset whose sum goes over $n$, we will adopt the strategy of picking a few candidate members which are prime, and then set an upper bound on the size of the rest of the candidates, so that the primary optimization routine is to find the largest product of a set of k members, each of whom is coprime to all the others, and all of them are below some bound $b$. When we have this routine and a good idea of how it behaves, we can adjust it to pick a few candidates above $b$, run the routine to pick the rest of the candidates below $b$, and show how far the result is from $(n/k)^k$.

So let us start by assuming $n$ large with respect to $k$, that we pick a few primes near and above $n/k$, and that we are about to run our routine to choose the rest of the $k$ numbers so that the result will have sum at most $n$ and consist of numbers mutually coprime.

We start with the largest primes just below our bound, which can be $n/k$ or a $b$ slightly less than $n/k$ if we want to be conservative. Since we are dealing with $k \lt n^{0.4}$ and $n$ sufficiently large, we can use a result of Baker, Harman, and Pintz to find more than $k$ many primes in an interval of length of order $(n/k)^{0.525}$ just below $b$. Likely the length is of order $k\log(n/k)$, but let us prepare for the worst. Call the length of this preliminary interval $L$.

Now we look for numbers in this interval which are close to $b$ and are the product of two large primes. Hopefully the smaller of the two primes will end up being larger than $L$, but if not, we then remove further multiples of this smaller prime from consideration. Each time we find such a candidate close enough to $b$, we remove the smallest member from our candidate set and replace it with this member, which is coprime to all other members chosen so far. To avoid future difficulties, we insist the smallest prime factor be above $n^{1/3}$, or something similar.

After we have picked all such numbers that we can find near $b$, and replaced the smallest primes with these, we now go on the next search, where we look for numbers with three (not necessarily distinct) large prime factors. Again to avoid future clashes, we assume the smallest prime factor is larger than $L$, or if not, we remove other multiples of this smallest prime factor from consideration.

The goal in all of this is to reduce the size of $L$. We could continue in this fashion, looking for numbers with four or five or more moderately large prime factors, and replace the smallest member of the set with each coprime candidate, until $L$ was small enough. Here is another method. Start from $b$, go toward 0, and search for all members whose smallest prime factor is above a certain bound $L$. Hopefully you have found $k$ many members before you have found $b-L$. Theory shows that $L$ is less than $b^{2/3}$.

I believe $L$ is smaller than $k\log(n/k)$ for the following reason. When we choose a number with smallest prime factor p, we eliminate a lot (but not all) of other candidates in the interval for coprimality, namely about 1/p many numbers in the interval. When we pick $j$ many such numbers (presumably coprime) with distinct smallest prime factors, we will find two numbers not having any of those smallest prime factors in an interval of length bounded above by $j^{4\log\log j}$ (I mention this in too much length in MathOverflow question 37679), which for small $j$ means we can pick $j$ representatives in a sizable interval and still have lots of coprime choices available, although now it would help to have $k$ small with respect to $\log(n/k)$ to have these statements hold.

If we decide on a greedy algorithm (pick $b$, then pick the largest number coprime to and less than numbers already picked) this will at worst terminate with $k$ numbers most of which are primes near $b$, but will include a few composites, and thus improve upon just picking the $k$ largest primes below $b$. On average $j$ above will be replaced by $j\log\log b$ , because we are picking mutually coprime numbers, and so the pool of choices will not deplete rapidly even with this greedy algorithm. Since these numbers are close to $n/k$, their product (and their LCM) will be close to $(n/k)^k$ for large $n$.

Gerhard "Should Have Started Working Greedily" Paseman, 2018.11.05.

$\endgroup$
0
$\begingroup$

I was hoping to come up with some proofs to answer this question for $k$ small with respect to $n$. Instead, I came up with more questions.

As in the other answer, the goal is to come up with a set of $k$ coprime numbers near $n/k$. Making some assumptions on the distribution of primes, we see that we can do this easily with prime numbers near $n/k$ as the farthest such prime from $n/k$ is conjecturally order $k\log n$ away from $n/k$, giving the product (equal to lcm) of this subset close enough to $(n/k)^k$ for government work (within half of this value). So I am morally convinced of the asymptotic value of $g(n,k)$ as $n$ grows with $k$ fixed.

I am now convinced that something stronger holds, which is in line with Aaron Meyerowitz's post.

Conjecture: Every interval of length $h(k)$ has at least $k+1$ integers which are mutually coprime.

What is $h(k)$? It is the Jacobsthal function $g(P_k)$ evaluated at the $k$th primorial, meaning,the length of the smallest interval for which one can guarantee a number in that interval with no prime factor among the first $k$ primes.

Although not a proof, it is easy to see why $h(k)$ "should" be of the right order. Namely, consider an interval of length $h(k)$ which has exactly one number $c$ coprime to $P_k$. If you don't pick this number, you are tasked with picking $k+1$ numbers mutually coprime and yet having one of $k$ different small time factors. You have to pick $c$ to have a chance.

This isn't a proof because the numbers may bunch up at one end of the interval. Another problem is that there are larger prime factors which may get in the way. However, $h(k)$ grows only slightly faster than the $k$th prime, so you won't find any small obstructing primes.

If one looks at the interval centered at $P_k$ of length $2p_{k+1} - 1$, one finds $k+2$ mutually coprime numbers and no more, so we know that any function measuring the length of an interval containing $k+1$ coprimes must grow like $k\log k$. We also have integers $N$ with $k$ prime factors with $g(N) \gt h(k)$, so there is a chance the conjecture above is false. However, since we want any set of $k+1$ coprime numbers in an interval, $h(k)$ is in there with a chance. Best of all (but without proof at the moment) $h(k)$ is independent of $n$, and as a result the asymptotics as $n$ grows to $g(n,k)$ will be tight.

Edit 2018.11.14.

I am still finding this subject challenging, so to improve my grip, I post a few minor results.

First, the conjecture is wrong. By results of Hajdu and Saradha on a disproof of a conjecture of Jacobsthal, there is a number N with 24 distinct prime factors for which $g(N) \gt g(P_{24})$, which means there is an interval of length 235 all numbers of which have a factor in common with N. The conjecture uses $h(24)=234$, so we have a longer interval which cannot have 25 coprime numbers in it.

To contrast with Aaron Meyerowitz's approach looking at residue classes, here is a brief presentation for 5 and for 6 coprimes. Pick an interval of length ten and look at the odd numbers in it. If the central number is a multiple of three, then this interval has six coprime numbers, as one of the even numbers next to the odd multiple of three is coprime to the five odd numbers. Otherwise, four of the odd numbers are mutually coprime, and three of the even numbers are coprime to the number three. Of the three even numbers, at most one has five as a factor and at most one has seven as a factor, leaving one even number coprime to the other odd numbers. So any interval of length ten has five mutually coprime numbers. (I assume implicitly that prime factors longer than the interval length can be safely ignored.)

If we try to find six coprime numbers in an interval of length twelve, we may end up with two odd multiples of five and two other odd multiples of three, giving only four odd numbers that are mutually coprime. This will not be enough. However, if we have an interval of length 14, we can choose a subinterval of length ten with only one odd multiple of three, and pick the six coprimes from that. So for $k=4$ and $5$ the conjecture holds. It also holds for smaller positive $k$, as can be easily confirmed.

For $k=6$, one quickly finds a configuration of ten odd consecutive numbers which has only five mutually coprime odd numbers (you need six), so this shows that one needs an interval length of 22 to get seven mutually coprime numbers. In general, by an argument similar to above, one needs an interval length of 1+C(k) to find k+1 mutual coprimes, where C(k) is like $ h(k)-1$ except a maximum is taken of $g(N)$ over all $N$ with $k$ distinct prime factors.

End Edit 2018.11.14.

Gerhard "So Let's Go Prove It" Paseman, 2018.11.07.

$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.