Wikipedia:Reference desk/Archives/Mathematics/2010 April 7

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

April 7

Linear Combinations

Given a list V of positive numbers, what is a fast way to count how many lists U of nonnegative numbers give U.V<=N for a given N? I've found 'figurate numbers', but I can't think of a way to adjust the formula. Black Carrot (talk) 00:23, 7 April 2010 (UTC)

I don't understand, neither the problem, nor the connection to linear combination, nor the connection to figurate number. Can you give a simple example? Bo Jacoby (talk) 08:17, 7 April 2010 (UTC).

The OP seems quite clear to me. U and V denote vectors (of positive, resp. nonnegative integers) and U.V denote their scalar product. So, given V:=(v₁,...,v__k) and a number n, we want to compute the cardinality c(n) of the set

$\{u\in \mathbb {N} ^{k}\,:\,\sum _{i=1}^{k}u_{i}v_{i}\leq n\}$

It should be easy to write a generating function for the sequence c(n); actually it should turn out to be a rational function. From the GF one can derive asymptotics on the c(n)'s. Of course, a first approximation is the volume of the pyramid containing the integer points U. See also Schur's theorem#Combinatorics for a very close problem.--pma 09:01, 7 April 2010 (UTC)

re the clarity of Black Carrot's question, the word he missed is "integers". More confusion was caused by the fact that linear combinations usually refer to vector spaces over a field, which the integers are not. That said, I didn't find it difficult to understand what the question was about. -- Meni Rosenfeld (talk) 09:42, 7 April 2010 (UTC)

Even doing this for real numbers, finding the volume of a convex figure, isn't that easy. If the number N isn't too large I'd do it simply by counting using loops which stop when the number gets too large. My guess is that this is an NP problem in essence for integers. Dmcq (talk) 10:37, 7 April 2010 (UTC)

It's not an NP problem, as NP is a class of decision problems, and here we want a number as output, not a yes/no answer. The problem is in #P. Maybe you meant that it is NP-hard? That's quite possible, given its resemblance to the knapsack problem.—Emil J. 11:57, 7 April 2010 (UTC)

Actually in this case the volume is very elementary. --pma 16:33, 7 April 2010 (UTC)

Oh sorry yes you're right, it is just a n-dimensional pyramid. I had a picture of a load of faces but that's wrong. In that case calculating the number of integer points may be fairly straightforward. Dmcq (talk) 17:13, 7 April 2010 (UTC)

Thanks for the explanation.

Bo Jacoby (talk) 12:12, 7 April 2010 (UTC).

Ehrhart polynomial may be helpful to answer the question.--RDBury (talk) 13:45, 7 April 2010 (UTC)

Yea, that is the answer. Actually it includes Schur's theorem, which is essentially the case where the convex L is an "orthogonal simplex" as in the OP's question. The first approximation $c(n)={\frac {n^{k}}{k!\prod _{i=1}^{k}v_{i}}}(1+o(1))$ (as $k\to \infty$) may be deduced by an elementary rescaling argument. And that also holds if the v₁,..,v_k and n are just positive real numbers .( as the OP possibly wanted?). --pma 16:33, 7 April 2010 (UTC)

In what sense it is the answer? How is the Ehrhart polynomial easier to compute than brute force enumeration of the points? Come to think of it, how do you compute the polynomial other than evaluating it in k + 1 points by aforesaid brute force enumeration, and interpolating?—Emil J. 16:53, 7 April 2010 (UTC)

That solution does look seriously scary even if it must be better than counting if N is large. The closest I've come to looking at anything like that is the Bellows theorem for flexible polyhedra. Thinking about it, it looks an interesting subject to spend some time on. Dmcq (talk) 17:28, 7 April 2010 (UTC)

Well, yes, I just meant that the important and non-trivial information is that it is a polynomial of degree k. For a general polytope, of course, I agree that the most efficient way of computing the polynomial may be interpolating k+1 points (anyway, a finite task). Also, I don't know the details for a general polytope, but in the special case of the OP, it is easy to write down a generating series for the numbers c(n). It is a rational function with poles at certain roots of unity (below I also use v₀:=1 together with the other positive integers v₁,..,v_k); precisely

$\sum _{n=0}^{\infty }c(n)x^{n}={\frac {1}{\prod _{i=0}^{k}(1-x^{v_{i}})}}.$

(To check it, just expand the RHS into a product of geometric series). To get a closed formula for the c(n) one should write the partial fraction decomposition of this rational function; then expand the simple fractions into power series. It is at least clear that this way one gets a polynomial formula for c(n) (in form of some linear combination of binomial coefficients -with a linear combination depending on n periodically ). For a given, small list V this can even be computed explicitly by hand. I've never seen a general formula (i.e. for a general V). Note that the pole with higher order is 1, corresponding to $C(1-x)^{-(k+1)}$ in the decomposition in simple fractions, and it is responsible of the growth of the c(n) (this is the Schur's computation I mentioned above). Writing the next terms with higher order one gets more refined asymptotics on the c(n). --pma 19:32, 7 April 2010 (UTC)

It finally struck me, this is a variant of the Coin problem, in how many ways can you give change with coins of various denominations. Dmcq (talk) 21:18, 7 April 2010 (UTC)

Exact, that is exactly the subject of Schur's theorem. Note that the OP's variant, consisting in "≤N", can be written in the usual form "=N" adding a v₀:=1. This produces a further factor 1/(1-x) in the GF, which makes sense, if we recall what is the effect of multiplying a power series by 1/(1-x). pma --84.221.209.68 (talk) 08:04, 8 April 2010 (UTC)

Let us also not forget that the Ehrhart polynomial only works for polytopes whose all vertices are integer lattice points. In this particular case, this condition amounts to n being an integer multiple of every v_i, which is a fairly nontrivial restriction.—Emil J. 10:46, 8 April 2010 (UTC)

Right!! So that's not exactly a generalization of the Schur's situation. Actually, outside of the case you are saying, the c(n) are not necessarily a polynomial sequence: e.g. , we can change n euros with 1 and 2 euros coins in $\scriptstyle \lfloor n/2\rfloor +1$ ways: 1, 1, 2, 2, 3, 3,... : I liked so much the Ehrhart polynomial, that I forgot about it :-) .--pma 13:12, 8 April 2010 (UTC)

Elementarily $\{u\in \mathbb {N} ^{k}\,:\,\sum _{i=1}^{k}u_{i}v_{i}\leq n\}=\{u\in \mathbb {N} ^{k}\,:\,\sum _{i=1}^{k}{\frac {u_{i}}{a_{i}}}\leq 1\}.$ where the k variables $\ a_{i}={\frac {n}{v_{i}}}$ are edges of a k-dimensional pyramide having volume $\prod _{i=1}^{k}{\frac {a_{i}}{i}}={\frac {\prod a_{i}}{k!}}$, which is PMA's approximation. Bo Jacoby (talk) 14:33, 8 April 2010 (UTC).

As many lattice points lie on the boundary of the pyramide, a slightly larger pyramide include the same lattice points as inner points. So I suppose that the expression ${\frac {\prod (a_{i}+{\frac {1}{2}})}{k!}}$ gives a better approximation to the requested number of lattice points. Bo Jacoby (talk) 08:21, 9 April 2010 (UTC).

Video Lectures on Topology and/or Differential Geometry

Does anyone know of any (good) video lectures on any of these two topics? Thanks. - DSachan (talk) 01:57, 7 April 2010 (UTC)

Open Courseware has some. I don't know if they are good. Youtube search also finds a bunch. You might also like The Catsters' youtube channel about category theory (I've heard positive reports about these videos). 66.127.52.47 (talk) 02:16, 7 April 2010 (UTC)

Thanks but OCW doesn't have any video lectures about these topics. What lecture did you see in youtube? I don't see any result. I want a good comprehensive kind of lecture series, not the bunch of 8 min. lectures given by highschoolers. The lectures by the lady seem nice, but as you said they are more on Category theory. - DSachan (talk) 02:28, 7 April 2010 (UTC)

Oh I see, there are several OCW courses on those topics but they only have written materials, not video. Sorry. On youtube I just typed "topology" and "differential geometry" into the search field and saw there were a bunch of hits. I didn't examine any of them. 66.127.52.47 (talk) 03:26, 7 April 2010 (UTC)

Additional: Terry Tao mentions this youtube (I haven't watched it) about Moebius transformations. Also, while they're not academic lectures, the topology videos from The Geometry Center are breathtaking. 66.127.52.47 (talk) 20:18, 7 April 2010 (UTC)

Lots of assorted math presentations at the MSRI website and their Internet Archive site 71.178.44.93 (talk) 20:43, 9 April 2010 (UTC)

Wow, those look great! I'm surprised I didn't know about them before. They seem to be very advanced though (research level), not that good for someone not already acquainted with a topic. 66.127.52.47 (talk) 06:57, 10 April 2010 (UTC)

Wow, that's unbelievably sexy. You made my day. Thanks. - DSachan (talk) 12:39, 10 April 2010 (UTC)