# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Sumset gives the sumset of a collection of sets or the h-fold sumset of a set

Contributed by:
Kevin O'Bryant

Professor of Mathematics

City University of New York

(College of Staten Island, The Graduate Center)

Professor of Mathematics

City University of New York

(College of Staten Island, The Graduate Center)

ResourceFunction["Sumset"][A gives the sorted set of sums a | |

ResourceFunction["Sumset"][ gives the sorted set of sums a |

ResourceFunction["Sumset"] gives all possible sums from taking one element in each of the given sets.

The sumset is also called the Minkowski sum in some analytic settings.

Uses Union, Flatten and Outer, so may not work as expected if some of the elements being added are themselves lists.

Computes ResourceFunction["Sumset"][2^{k},A] for enough values of k to compute ResourceFunction["Sumset"][h,A], simplifying along the way, so this is faster than naive implementations. (This is akin to using a power tree method to compute a power.)

Compute the 6-fold sumset of a set of integers:

In[1]:= |

Out[1]= |

Compute the sumset of points in the plane:

In[2]:= |

Out[3]= |

Compute the sumset of points in 3-space:

In[4]:= |

Out[6]= |

The expected size of Complement[Range[2,*n*],Sumset[2,A]] is just under 10, if A is a random subset of Range[1,*n*] (reference is *Many Sets have More Sums than Differences, G. Martin and K. O'Bryant, *Additive combinatorics, 287--305, CRM Proc. Lecture Notes, 43, Amer. Math. Soc., Providence, RI, 2007):

In[7]:= |

Out[9]= |

As h grows, Sumset[*h*,A] grows to contain the interior of a polygon (scaled to h):

In[10]:= |

Out[11]= |

Wolfram Language 13.0 (December 2021) or above

- 1.0.0 – 03 June 2024

This work is licensed under a Creative Commons Attribution 4.0 International License