Addition chains meet postage stamps: Number theory helps multiplication

Title:

 

Addition chains meet postage stamps: Number theory helps multiplication

 

 

Abstract:

 

Addition chains are integer sequences such as (1,2,4,8,10), where each element is a pairwise sum of earlier elements, for example 8 = 4+4.  They are commonly used to optimize repeated multiplication: if x is given, and x^10 is required, one computes successively x^2, x^4, x^8 and then x^10 = x^2 * x^8. The multiplication operation may be costly, for example multiplication of large matrices, or of long integers in cryptography, so it is desirable to reach the target power with as few multiplications as possible.

 

Postage stamps are another known problem in additive number theory. The problem is to find a sequence of integers ("stamps") such that all integers from 1 up to some target value N can be represented as the sums of one or two stamps (so that any postage fare can be paid by 1 or 2 stamps). Such sequences, or "additive bases", have been studied mainly as a purely mathematical endeavor. Perhaps surprisingly, the existing literature seems to contain no connection between these two seemingly similar notions: addition chains and postage stamps.

 

In this presentation, I will describe a slightly different repeated multiplication task, and I will show how this task can be optimized by constructing a sequence of integers which combines the flavors of addition chains and postage stamps. This optimization has been successfully applied in a Bayesian clustering problem where the "multiplication" is a costly operation known as subset convolution.

 

 

About the presenter:

 

Jukka Kohonen is a doctoral student at the University of Helsinki in the Mathematics and Statistics department. He has previously done research on the optimization of wireless networks. Currently his main research interest is in Bayesian clustering methods.