Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we are given a representation of a finite series of natural numbers:

$\sum_{i=0}^N{c_i x^i}$

The representation is essentially an expression that is a rational function of two polynomials.

Is it possible to add/subtract this series repeatedly to get a result that contains only part of the series?

A simple formulation of the problem

We can forget that we have a series, for a moment, and consider it more like a tile. It contains a set of numbers on it that are in a particular order that cannot be changed. It's basically striaght; it just contains this set of numbers on a line.

Now we actually have many copies of this same tile, and some are oriented differently. The different orientation comes from the fact that the tile could be on a line into another dimension. For example, one tile may start at coordinates (0,0) and end at coordinates $(0,N)$. Another may start at (0,0) and end at $(N,0)$. All tiles are essentially the same ordered set of numbers that start at one point in $m$ dimensions and end at another point.

There is essentially one operation that we can perform. We can take the difference of numbers at a given point. For example, if the sequence is (1,2,3), we can take one tile that starts at (0,0) and proceeds to (0,2). Subtract another tile that starts at (0,0) and proceeds to (2,0). This would cancel out the ones in both tiles, since we subtract the one at (0,0) in the second tile from the one at (0,0) in the first tile.

I'm wondering if we can somehow add and subtract these tiles so that only a single number remains. It may be that more than one location contains this same number.

There are some rules, so an example and explanations will probably help.

Could you give an example?

Here's an example. Consider the finite series $10 + 200x$.

We can repeatedly add and subtract (scalar multiples of) this series (and a similar series) in the $x,y$ "plane" to end up with $200x$, only part of the series.

Here's how:

(0) Start with $10+200x$.

(1) Subtract $10 + 200y$. This eliminates 10 and we're left with $200x-200y$.

(2) Add $(10+200x)\cdot y / x$. This eliminates the $-200y$ in the previous result and adds $10\cdot y / x$, resulting in $200x+10\cdot y / x$.

(3) Subtract$(10+200y)\cdot y / x$. This eliminates $10\cdot y / x$, subtracts $200\cdot y^2 / x$, and we're left with $200x - 200\cdot y^2 / x$

(4) Add $((10+200x)\cdot y / x)\cdot y / x$. This eliminates the $-200\cdot y^2 / x$ in the previous result and adds $(10\cdot y / x)\cdot y / x$, resulting in $((200x+10)\cdot y / x)\cdot y / x$.

...

We repeatedly add and subtract pieces of the series this way. It can be shown that the result of this infinite series is $200x$, which is only part of the original series.

I'd like to know if we can add and subtract larger series similarly (but possibly in more dimensions) to end up with only a single coefficient or piece of the series.

For example, If we consider the series $1 + 2x + 3x^2$, we may be able to eliminate $1$ and $3x^2$ from this series by a set of careful additions and subtractions.

I don't know which branches of mathematics this deals with, but I'm hoping an expert can provide me with some direction.

Why are you doing this/ What's your motivation?

Results from this "puzzle" would help speed up an algorithm significantly, so I'm interested in publishing this result with whoever helps me. I know MO's position on algorithms, but I believe that this is more of a "tiling" or mathematics question than a question on an algorithm.

I'd like to know all branches of mathematics that deal with this question, and where I can go, or who I can go to, that will help me solve the general problem.

Some additional notes: The value of $x$ is not allowed to be modified. We can rewrite $x$ as another variable (I rewrote $x$ as $y$ above, for example). We are also allowed to "shift" the series (for example, multiply by $y / x$ as done above). Cancellation is, of course, allowed - and it may be done infinitely many times. These are the only allowable operations.

Also, I am particularly interested in the coefficient in the middle of the series.

One additional consideration: methods that use fewer variables are preferred.

share|improve this question
3  
It is really unclear to me what operations you're allowing. Can I change the value of x, for example? If that's the case, then it's easy to show that you can extract any particular coefficient by picking suitable values of x. This is just linear algebra. –  Qiaochu Yuan Oct 19 '10 at 13:11
    
Sorry, but you can't change the value of x. You can only rewrite the variable x as another variable (y, for instance). –  Generator Oct 19 '10 at 13:14
    
Please use \dot or \cdot for a multiplication dot in LaTeX, and please use proper parenthesization so we can decipher what's going on. I have no clue how "division by $xy$" fits into your framework, but you seem to do it and similar things repeatedly; it seems likely to me that whatever you're asking about is not sufficiently well-defined to admit a meaningful answer. –  JBL Oct 19 '10 at 13:33
    
@JBL: Thanks for the LaTeX help. There are really only two operations allowed, and I've edited the question to reflect this. –  Generator Oct 19 '10 at 13:46
2  
If this question can be formulated as studying the ideal generated by a polynomial or polynomials in some polynomial ring, then probably something can be said about it. Expressions Q(x,y)P(x) + R(x,y)P(y), for example. –  Charles Matthews Oct 19 '10 at 15:19
show 8 more comments

1 Answer

up vote 5 down vote accepted

I'm not sure I fully understand the problem, but here goes. Start with $10+200x$. Multiply by $20x$ to get $200x+4000x^2$. Subtract $(10+200x)(400x^2)$ to get $200x-80000x^3$. Add $(10+200x)(8000x^3)$ to get $200x+1600000x^4$. Keep going. The result of this infinite procedure is, in some sense, $200x$, and you don't even need $y$ to do it.

All I'm doing is solving $(10+200x)Q(x)=200x$; you get $Q(x)=20x-400x^2+8000x^3+\dots$, which tells you what to add and subtract.

If you want to eliminate 1 and $3x^2$ from $1+2x+3x^2$, solve $2x=(1+2x+3x^2)Q(x)$ one way or another to get $Q(x)=2x-4x^2+2x^3+8x^4-22x^5+\dots$, and that tells you what you have to do.

If this doesn't solve your problem, then you may have to rethink your presentation.

EDIT: In view of OP's comment, maybe this is closer to what's wanted. Let $f(x)=a+bx+cx^2$ where $a,b,c$ are unknown. Here's how to pick out $bx$: $${\bigl(f(x)-f(y)\bigr)(x^2-z^2)-\bigl(f(x)-f(z)\bigr)(x^2-y^2)\over(x-y)(x^2-z^2)-(x-z)(x^2-y^2)}x=bx$$ I don't see how to do it with just $x$ and $y$, indeed, I think that if you start with a polynomial with $n$ terms you'll need $n$ variables. But I think that you can always pick out any term you like if you use that many variables, and I think you can work out how to do any particular case once you've worked out how the formula above does its job.

share|improve this answer
    
Please forgive me. I neglected a major point: We don't know the coefficients. We have an expression for a rational generating function instead. –  Generator Oct 20 '10 at 5:09
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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