jump to navigation

Generalized Nonaveraging Integer Sequences January 9, 2015

Posted by Dennis in Uncategorized.

Everybody who participated in RSI 2009 from this blog have now just finished their undergraduate degrees. I think it’d be interesting to have an update to see how everybody is doing.

I think in the future, I’ll add posts here either to 1) explain intuitively what happens in a paper of mine or 2) write the proof or idea of something that is hard for me to find in the literature. The audience for 1) is going to be really small, considering the lack of papers and people who read them (but I feel sorry for them), and 2) would be to help myself learn.

This time, I’ll try to outline intuitively what went on in my RSI project 5 years ago, the reason being that the main ideas (I think) are pretty well-disguised behind the technical details, which are really just a bunch of casework. The paper is here: http://arxiv.org/pdf/1107.1756.pdf.

As for motivation, we recall that there is the open problem of trying to find the largest subset S of \{0,1,\ldots,N\} that contains no three term arithmetic progression. Most of the research has been focused on finding asymptotics for the size of S given large N. I won’t claim enough familiarity with the current literature to give the best current bounds, but I dimly recall there was a lower bound constructed by Elkin and an upper bound by Bourgain five years ago, and that they were the best then.

Disregarding the current literature, the most naive way to approach this problem is to use the greedy algorithm. Namely, you start with S empty, and then repeatedly add the smallest number possible that does not violate the condition that there is no 3-term arithmetic progression.

It turns out that the greedy algorithm generates a sequence S that contains precisely the integers that have only 0 or 1’s as digits when expanded in base 3. This extremely explicit solution is nice, but we can also easily tell that it is horrible asymptotically. For example, the greedy algorithm gives |S|=\Omega(n^{\log_3(2)}), while Elkin’s construction alluded to above gives |S| = \Omega(\frac{n}{2^{2\sqrt{2}\sqrt{\log_2(n)}}}\log^{1/4}(n)).

The condition that the sequence has no three term arithmetic progression is equivalent to avoiding (nontrivial) solutions to x+y=2z, where nontrivial here means ruling out $x=y=z$. We would like to generalize this. For example, if you generate the greedy sequence that contains no solution to x+y+z=3w, where x,y,z,w are all different, you get numbers of the form 3M + R where M is a number whose base 4 representation has only 0’s and 1’s, and R\in \{0,1,2,3,4\}. This is a result due to Layman, in a short paper in the journal of integer sequences.

What happens if we consider avoiding solutions to
\begin{aligned}  a_0x_0+\cdots+a_nx_n = (a_0+\cdots+a_n)x_{n+1}  \end{aligned}
where all the x_i‘s are different? (There is also the related (I think slightly easier but still hard) problem where you instead consider where not all the x_i‘s are the same, but let’s focus on this case for now.)

In general, I think we don’t understand this at all (or at least we didn’t understand it 5 years ago). From generating these sequences with a computer, it seems like, if you have a bunch of terms that are close together, then that forces the next terms in the sequence to be farther apart. Similarly, if a bunch of terms are far apart, then the next terms in the sequence are closed together. This makes complete sense heuristically.

I wish I still had the actual graphs to give an idea, but the graph of the sequence would typically be flat at the beginning, suddenly grow because of the terms bunched together. Then, since the terms are spread out, it would suddenly become flat again. This would repeat. Instead of simply cycling, the times where the graph is either flat or growing really fast increases with each iteration. I think they increase geometrically, but it was hard to compute enough terms to see.

In some very special cases, this pattern is so extreme that the part where the graph is growing really fast is instead a perfect jump. This is because the terms in the beginning are so bunched together that there are simply no gaps to stick any more terms. Consider, for example, the graph of the sequence that avoids x_1+x_2+x_3+x_4=4x_5:


My RSI paper was just to try to find these some of these sequences and their closed forms (for example the one above). The idea is the same as Layman’s paper, where the closed form is cM+R, where c is some number, R is some set of initial terms, and $M$ are the integers with 0’s and 1’s in base d representation, where d=a_0+\cdots+a_n+1. Basically, the elements in R prevent anything else less than $c$ from being in the sequence, and c is so large that you can treat M and R independently when plugging into the equation a_0x_0+\cdots+a_nx_n=(a_0+\cdots+a_n)x_{n+1}. As you can tell, this only happens in extremely special cases, but, in particular, it encompasses the case where all the a_i‘s are 1.

In general, I think it’s interesting to try to find the growth rate of these sequences, but my guess is that it is difficult. In fact, I didn’t found anything in the literature that beats the silly counting argument (other than heuristic arguments) during RSI in terms of an upper bound. It’s messy, yet not random.

A Puzzle June 25, 2010

Posted by genericme in Uncategorized.

Consider a set of n objects from which m are drawn randomly at a time, with replacement.  What is E(n, m), the expected number of draws I have to make to have drawn all of the objects?

I have yet to find a satisfactory closed-form expression for even E(n, 1).  I obtain an ugly series in terms of Stirling numbers of the second kind.   However, I suspect that E(n, 1) is asymptotically linear:

Is this a well-known problem?

Random updates June 14, 2010

Posted by Akhil Mathew in Uncategorized.

It’s been another two months already since anyone last posted here, hasn’t it?

So, first of all, Damien Jiang, Anirudha Balasubramanian, and I have each uploaded the papers resulting from our RSI projects to arXiv.  I’ve been discussing the story of my project on representation theory and the mathematics around it on my personal blog (see in particular here and here).  There are others from the program who have placed their papers on arXiv as well (but are not involved in this blog).

I’d like to congratulate my friend and fellow Rickoid Yale Fan for winning the Young Scientist award at the International Science and Engineering Fair for his project on quantum computation (which deservedly earned him the title “rock star”).  I also congratulate his classmate and fellow rock star Kevin Ellis (who did not do RSI, but whom I know from STS) for winning the (again fully deserved) award for his work on parallel computation.  There is a press release here.

RSI 2010 is starting in just a few more days.  I’m not going to have any involvement in the program myself (other than potentially proofreading drafts of kids’ papers from several hundred miles away), nor do I know much about what kinds of projects (mathematical or otherwise) will be happening there.  I think I’d be interested in being a mentor someday—maybe in six years time.  I’m going to be doing a project probably on something geometric this summer, but it remains to be seen on what.

I don’t really know what’s going to become of this blog as we all now finish high school and enter college.  It looks like most of us will be in Cambridge, MA next year; this is hardly surprising given the RSI program’s location there.  Also, just to annoy Yale, I’m going to further spread the word that he is going to Harvard.

If anyone from RSI 2010 wants to join/revive this blog, feel free to send an email to deltaepsilons [at] gmail [dot] com.

Siemens October 7, 2009

Posted by Damien Jiang in Uncategorized.
Tags: , ,

Unfortunately the depth and breadth of my mathematical knowledge are not as awesome as Akhil’s. So, I’ll talk about something else related to math.

I, like probably every other contributor to this blog, submitted my research paper to the Siemens competition about a week ago. Despite the incredible amount of editing I did at RSI, I realized, to my dismay, that the bulk of the editing was still to be done.


USAMO 1973 #5 August 21, 2009

Posted by lumixedia in Uncategorized.
1 comment so far

The claim this problem makes looks obvious but turns out to be…actually, not much harder than it looks. The solution has one clever moment but I think you can avoid it by a little more algebra, though it’s not interesting enough to write out.

USAMO 1973 #5. Show that the cube roots of three distinct prime numbers cannot be three terms (not necessarily consecutive) of an arithmetic progression. (more…)

The RSI experience continued August 6, 2009

Posted by Dennis in General, Mathematical research, Uncategorized.

The previous post did a nice job in describing the process of our math research. In addition to the research, the math students form a special group, and it really is fun.

Instead of going to mentorships at labs all day, we only have an hour,  so for me, much of the time was spent at the computer lab. And there, we can see many of the math students come and go during the day. After a few days, it is obvious which students do their work very late at night and which students work in the morning.

We also have funny little things that happen that make the experience more interesting. Not_trig brought the culture of tetris playing from his school, and I learned a very slow version of his “T-spin”. Ubuntu and Pokman Cheung are popular words we like to throw around. Ubuntu came from the Linux computers and Pokman Cheung coauthored a book in quantem calculus. We also noticed how dedicated Akhil was to this blog, which can be seen from all the Algebra posts and from his daily checking of the blog stats.

There is a subgroup of the math students that researched representation theory. I am not an “Etingofling”, so I don’t really know much about what goes on in there. Except the Etingoflings use a lot of words that end with “orphism” and view Etingof as a god at math.

Outside of math, you can play frisbee, ping pong, soccer, watch movies or go to all sorts of activities in the evening. Unfortunately, I was one of those who worked in the morning, so I slept through most of those, but frisbee is fun.

I guess, even though it’s hard to put into words, it really is a fun time and those six weeks seem so short when it’s time to leave. It feels like I lived half my life at RSI, but yet that half a life only lasted for 7 days.

An Interesting Problem July 23, 2009

Posted by genericme in Uncategorized.

Though this post isn’t necessarily characteristic of what I’d like to post on in the future, I have an interesting problem that I must share with you all.  To encourage everyone to try it, I will not include a solution.

Two points, A and B, sit on the x-axis.  Point A is at the origin, and point B is at (L, 0).  At time t = 0, B starts moving at a constant speed u perpendicular to the x-axis, while A starts moving with constant speed v such that its velocity vector is always pointing in the direction of B.  Assume v > u.  At what time will the points meet?

This problem is much harder than it seems.  It comes from a book of physics problems, but I’d really consider it a math problem.  I’d like to note that I know of two solutions: an extremely clever solution that requires only a trivial amount of calculus, and a long solution that requires quite a bit of calculus (but that still requires a clever substitution).  The latter solution is due to Eric Larson, who solved this problem a few days after I gave it to him.  However, I know of no one who has independently thought of the clever solution, and I’ll be extremely impressed if you do!  If you’ve seen this problem before, please don’t reveal the solution.

Additive Combinatorics July 22, 2009

Posted by lhstephens in Uncategorized.

My project at RSI is in additive combinatorics, which is a field of math, which extends the notions of set over operations. Here is a brief introduction to some of the terminology and theorems in the field.

Additive combinatorics studies subsets of abelian groups. To study these sets, additive combinatorics uses theorems and notation from both graph theory and set theory. An additive set {A} with respect to an abelian group {Z} is a set {A \subset Z}. The group Z is referred to as an ambient group. Normally, the group {Z} is the integers over addition or {\mathbb{Z} , +}. (more…)

USAMO 2009 #5 July 19, 2009

Posted by Damien Jiang in Problem-solving, Uncategorized.
Tags: ,
1 comment so far

I like Olympiad geometry. Therefore, I will give my solution to this year’s USAMO #5; I was rather happy with my solution.

5. Trapezoid {ABCD}, with {\overline{AB}||\overline{CD}}, is inscribed in circle {\omega} and point {G} lies inside triangle {BCD}. Rays {AG} and {BG} meet {\omega} again at points {P} and {Q}, respectively. Let the line through {G} parallel to {\overline{AB}} intersects {\overline{BD}} and {\overline{BC}} at points {R} and {S}, respectively. Prove that quadrilateral {PQRS} is cyclic if and only if {\overline{BG}} bisects {\angle CBD}.


IMO 2009 #1 July 18, 2009

Posted by Martin Camacho in Problem-solving, Uncategorized.
Tags: ,

The 2009 IMO was a few days ago – in this post I tackle what I think is one of the easier IMO problems, IMO 2009 #1.

The question is as follows:

Let {n} be a positive integer and let {a_1,a_2,a_3,\cdots,a_k} ({k\ge 2}) be distinct integers in the set {1,2,\cdots,n} such that {n} divides {a_i(a_{i+1}-1)} for {i=1,2,\cdots,k-1}. Prove that {n} does not divide {a_k(a_1-1)}.