Wikipedia:Reference desk/Archives/Mathematics/2008 October 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 19

The number of arithmetic progressions possible

Hello. The question is: How many finite k-term Arithmetic Progressions's are possible in the set {1,2,3,...m}. Thanks--Shahab (talk) 05:05, 19 October 2008 (UTC)

Well, assuming m >= k, the set will be non-empty, and less than mCk, but I can't see an obvious way to count them. -mattbuck (Talk) 05:58, 19 October 2008 (UTC)

SAy that each of such arithmetic progressions is determined by its first term, and by the increment h. If h=1 there are m+k-1 of them, if this number is positive, because you can start with 1,..,m-k+1, and from m-k on there is no room left: so with h=1 they are $(m-k+1)_{+}$ (here $a_{+}$ denotes the positive part of $a$). Similarly you can count how many of them are there with h=2,3,.., and you end up with your answer in form of a sum over all natural $h$, where however only finitely many terms are nonzero. Enjoy it! The next step could be: find an asymptotic for $\sum _{h\in \mathbb {N} }(m-hk+h)_{+}$, say with $m/k\to \infty$, approximating the sum with an integral. (e.g. ~$m^{2}/2(k-1)$) --PMajer (talk) 08:02, 19 October 2008 (UTC)

I think I have got it by your approach. h however also must be bounded: (k-1)h < m, so I guess the sum (m-hk+h)should be from 1 to $\lfloor {\frac {m-1}{k-1}}\rfloor$. Thanks--Shahab (talk) 08:18, 19 October 2008 (UTC)

Right, but that's automatically included writing $(m-hk+h)_{+}$, which is 0 for larger h --PMajer (talk) 08:46, 19 October 2008 (UTC)

Pardon me, but can you explain how to find the asymptotic. I actually need to show that the number is at least ${\frac {m^{2}}{2k}}$. A closed form expression by your technique is $m\lfloor {\frac {m-1}{k-1}}\rfloor -{\frac {k-1}{2}}\lfloor {\frac {m-1}{k-1}}\rfloor {\Big (}\lfloor {\frac {m-1}{k-1}}\rfloor +1{\Big )}$. Now how can I show this quantity to be at least ${\frac {m^{2}}{2k}}$. Thanks a lot.--Shahab (talk) 13:47, 19 October 2008 (UTC)

For bounds and asymptotics one possibility is: factor out $m^{2}$ from the sum of m-h(k-1) (for 0<h<m/(k-1), then look at the resulting sum as a Riemann sum of a suitable function. But since you have that nice closed formula, maybe you can factor out the term $\lfloor {\frac {m-1}{k-1}}\rfloor$, then bound the floor terms in it from below and above using $\lfloor x\rfloor -1<x\leq \lfloor x\rfloor$ (taking into account the sign) and see what happens...--PMajer (talk) 15:08, 19 October 2008 (UTC)

I presume you mean $\lfloor x\rfloor \leq x<\lfloor x\rfloor +1$. That approach doesn't work. I get $m\lfloor {\frac {m-1}{k-1}}\rfloor -{\frac {k-1}{2}}\lfloor {\frac {m-1}{k-1}}\rfloor {\Big (}\lfloor {\frac {m-1}{k-1}}\rfloor +1{\Big )}>{\frac {m^{2}}{2(k-1)}}-{\frac {m}{2}}-{\frac {k}{2(k-1)}}$. This is short of what I need.--Shahab (talk) 15:17, 19 October 2008 (UTC)

Yes sorry I meant with floor inside :)

Otherwise you can think your closed formula like a second degree polynomial $p(x)$ computed in $x_{0}=\lfloor {\frac {m-1}{k-1}}\rfloor$. We are in the half-line where $p'(x)$ has a definite sign so you can have bounds of the form $p(a)<p(x_{0})<p(b)$. Can you obtain $m^{2}/2k$ this way? But by the way first check your formula. Seems OK, but maybe you get a better form using the (equivalent) bounds for h in the sum: $(k-1)h\leq m$, so $x_{0}=\lfloor {\frac {m}{k-1}}\rfloor$. --PMajer (talk) 15:31, 19 October 2008 (UTC)

Isn't $(k-1)h<m$ as $(k-1)h=m$ would make $a+(k-1)h>m$ whatever initial term a we choose? --Shahab (talk) 16:26, 19 October 2008 (UTC)

I just mean that the term in the sum corresponding to $(k-1)h=m$ is 0. Summarizing: your number N of arithmetic progressions is the value of $p(x):=mx-{\frac {k-1}{2}}x(x+1)$ computed in a point (i.e. the integer one), $x_{0}$ between $a:={\frac {m}{k-1}}-1$ and $b:={\frac {m}{k-1}}$. Observe that $p(x)$ has a maximum exactly at the midpoint between a and b. This gives you $p(a)=p(b)\leq N\leq p({\frac {a+b}{2}})$, that is I guess ${\frac {m^{2}}{2(k-1)}}-{\frac {m}{2}}\leq N\leq {\frac {m^{2}}{2(k-1)}}-{\frac {m}{2}}+{\frac {k-1}{8}}$, or something similar, in any case sharp bounds, in that $x_{0}$ may well fall in an endpoint or in the midpoint of the interval $[a,b]$. In particular, the inequality $N\geq m^{2}/2k$ cannot be always true, even if is true for large $m$, e.g. for $m>k(k-1)/2$. It also means that a more precise approximation needs non-algebraic terms. I did not check everything so don't take it for sure. PMajer (talk) 17:45, 19 October 2008 (UTC)

Gourami, genetic mutation?

Duplicate question removed - see Wikipedia:Reference_desk/Science#Genetic_mutation-_Double_tail_gourami. Gandalf61 (talk)

Countable metacompactness of the Sorgenfrey plane.

Does anyone know whether the conjecture that the Sorgenfrey plane is countably metacompact, is solved? It is not metacompact (I am pretty sure) but determining countable metacompactness is a lot less trivial. I would appreciate any references.

Thanks in advance.

Topology Expert (talk) 14:04, 19 October 2008 (UTC)

According to the excellent table at the end of Counterexamples in Topology, it is countably metacompact. Algebraist 15:45, 19 October 2008 (UTC)

Thanks very much for that reference, sounds good. I'm glad I looked at this question. Dmcq (talk) 21:34, 19 October 2008 (UTC)