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

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 $\backslash sum\_\{h\backslash in\backslash N\}(m-hk+h)\_+$, say with $m/k\; \backslash to\backslash 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 $\backslash lfloor\; \backslash frac\{m-1\}\{k-1\}\backslash 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 $\backslash frac\{m^2\}\{2k\}$. A closed form expression by your technique is $m\backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor-\backslash frac\{k-1\}\{2\}\backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor\backslash Big(\backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor+1\backslash Big)$. Now how can I show this quantity to be at least $\backslash 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\lfloor\frac{m-1}{k-1}\rfloor, then bound the floor terms in it from below and above using

::I presume you mean . That approach doesn't work. I get $m\backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor-\backslash frac\{k-1\}\{2\}\backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor\backslash Big(\backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor+1\backslash Big)>\backslash frac\{m^2\}\{2(k-1)\}-\backslash frac\{m\}\{2\}-\backslash 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=\; \backslash lfloor\backslash frac\{m-1\}\{k-1\}\backslash rfloor$. We are in the half-line where $p\text{'}(x)$ has a definite sign so you can have bounds of the form

using the (equivalent) bounds for h in the sum: $(k-1)h\; \backslash leq\; m$, so $x\_0=\backslash lfloor\backslash frac\{m\}\{k-1\}\backslash rfloor$.

--PMajer (talk) 15:31, 19 October 2008 (UTC)

:::Isn't 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-\backslash frac\{k-1\}\{2\}x(x+1)$ computed

in a point (i.e. the integer one), $x\_0$ between $a:=\backslash frac\{m\}\{k-1\}-1$ and $b:=\backslash 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)\backslash leq\; N\; \backslash leq\; p(\backslash frac\{a+b\}\{2\})$, that is I guess $\backslash frac\{m^2\}\{2(k-1)\}-\backslash frac\{m\}\{2\}\; \backslash leq\; N\; \backslash leq\backslash frac\{m^2\}\{2(k-1)\}-\backslash frac\{m\}\{2\}\; +\backslash 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\backslash 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)

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

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)