DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Polynomial Approximation of Computationally-Hard Sequences

Speaker: Aviezri Fraenkel, Weizmann Institute, Israel

Joint Talk with Mathematics Colloquium

Date: Thursday, December 6, 2007 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The question whether an m-tuple (x₁,...,x_m) in Z_{≥ 0}^m is in (a¹,...,a^m), where the aⁱ are given integer sequences, can sometimes be decided efficiently (in polynomial time). More often, the answer is unknown, the best known algorithms being exponential. We present a polynomial approximate algorithm for deciding this question for some sequences a_i. Specifically, we consider the complementary sequences a_n=mex{a_i, b_i : 0 ≤ i < n}, b=a_n + |_ n/k _| (sequences A102528/9 in Sloane's encyclopedia for k=2). Using Fekete's Lemma we show that the polynomially computable sequences s_n=|_n α_|, t_n=|_n β_| where α = (√(17)+3)/4, β=α+1/2 are very good approximations, namely, s_n-1 ≤ a_n ≤ s_n, t_n-1 ≤ b_n ≤ t_n for all n ≥ 1 (k=2). We conjecture that the percentage of n for which a_n=s_n-1 is about 73%, a_n=s_n, 19%, a_n=s_n-2, 8%. Similar results for b_n, t_n. Analogous results for every fixed k>1. Existence of a limiting distribution, with one of the percentages dominant, would lead to first probabilistic algorithms for determining the winning positions of certain impartial games, where the (a¹, ..., a^m) are the second player winning positions.

Joint work with Udi Hadad.