Beck-Robins 2.1/2.3(a) Fix Positive Integers ✓ Solved

1. (Beck-Robins #2.1/2.3(a)) Fix positive integers

1. (Beck-Robins #2.1/2.3(a)) Fix positive integers a, b, c, d. (a) Suppose gcd(a,b) = gcd(c,d) = 1 and a/b < c/d. Let P ⊆ R be the interval [a/b, c/d]. Compute L_P(t) and L_{P^o}(t). (b) Let T be the triangle with vertices (0,0),(a,0),(0,b). Use Homework 2 #3 and an appropriate theorem to compute L_T(t) and Ehr_T(z). 2. (Beck-Robins #2.4) Let P⊆R^m and Q⊆R^n be polytopes. (a) Prove #((P×Q)∩Z^{m+n}) = #(P∩Z^m)·#(Q∩Z^n). (b) Conclude L_{P×Q}(t)=L_P(t)L_Q(t). 3. (Beck-Robins #2.9) Let d≥0. (a) Prove z^d/(1−z)^{d+1} = ∑_{k≥0} (k choose d) z^k. (b) Conclude 1/(1−z)^{d+1} = ∑_{k≥0} (d+k choose d) z^k. 4. (Beck-Robins #2.10) For t,k∈Z and d>0, prove (−1)^d (−t+k choose d) = (t+d−1−k choose d). 5. (Beck-Robins #2.23) Prove that if Q contains the origin, then Ehr_{BiPyr(Q)}(z) = (1+z)/(1−z) Ehr_Q(z). 6. (Beck-Robins #2.26) Let P be the self-intersecting polygon defined by segments [(0,0),(4,2)], [(4,2),(4,0)], [(4,0),(0,2)], [(0,2),(0,0)]. Show that Pick's theorem does not hold for P.

Paper For Above Instructions

Abstract. This document addresses six exercises from Beck and Robins concerning one-dimensional Ehrhart quasi-polynomials, Ehrhart polynomials for a standard right triangle, multiplicativity of lattice-point counts in Cartesian products, binomial generating-function identities, a negative-binomial identity, the Ehrhart series of a bipyramid, and a counterexample to Pick's theorem for a self-intersecting polygon. Short proofs and explicit formulas are provided.

1. Interval and triangle Ehrhart counts

Let P = [a/b, c/d] with gcd(a,b)=gcd(c,d)=1 and a/b < c/d. For integer t≥0 the dilate tP = [ta/b, tc/d]. Thus the number of integer lattice points in tP is the count of integers k satisfying ta/b ≤ k ≤ tc/d. Hence

L_P(t) = #{k∈Z : ceil(ta/b) ≤ k ≤ floor(tc/d)} = floor(tc/d) − ceil(ta/b) + 1.

This expression is a degree-1 Ehrhart quasi-polynomial with period lcm(b,d); equivalently its leading term equals the length (c/d − a/b) t and the constant term and the periodic fluctuation are captured by the floor/ceil terms (see Beck & Robins (2007) for quasi-polynomial structure).

The interior count L_{P^o}(t) is the number of integers k satisfying ta/b < k < tc/d, so

L_{P^o}(t) = max(0, floor((tc−1)/d) − floor((ta)/b)) = floor((tc−1)/d) − ceil(ta/b) + 1

or more compactly L_{P^o}(t) = floor(tc/d − ε) − ceil(ta/b) + 1 with ε→0+, equivalently computed using shifted floor identities. These floor/ceil formulas are standard one-dimensional Ehrhart expressions (Beck & Robins, 2007).

Triangle T with vertices (0,0),(a,0),(0,b)

The triangle T is a lattice polygon (vertices integral). Ehrhart's theorem implies L_T(t) is a polynomial of degree 2 with leading coefficient equal to the area of T, area(T) = ab/2. The boundary lattice point count B on T equals a + b + gcd(a,b) (counting lattice points on each edge and removing overlaps). Using the two-dimensional Ehrhart formula (equivalent to Pick's theorem),

L_T(t) = area(T) t^2 + (B/2) t + 1 = (ab/2) t^2 + ((a + b + gcd(a,b))/2) t + 1. (1)

The Ehrhart series Ehr_T(z) = ∑_{t≥0} L_T(t) z^t has the rational form h(z)/(1−z)^3 where h(z) is the h*-polynomial of degree at most 2 with coefficients determined by the standard formula h_0 = 1, h_1 = B/2 − 1, h_2 = area − B/2 + 1 (Stanley, 1997). Concretely,

Ehr_T(z) = [1 + ((a + b + gcd(a,b))/2 − 1) z + ((ab/2) − (a + b + gcd(a,b))/2 + 1) z^2] / (1 − z)^3. (2)

2. Lattice points in Cartesian products

If P⊆R^m and Q⊆R^n are polytopes, every lattice point in P×Q ⊆ R^{m+n} is a pair (p,q) with p∈P∩Z^m and q∈Q∩Z^n. The map (p,q) ↦ (p,q) is a bijection between (P∩Z^m)×(Q∩Z^n) and (P×Q)∩Z^{m+n}, so

#((P×Q)∩Z^{m+n}) = #(P∩Z^m) · #(Q∩Z^n).

Applying this to dilates tP and tQ yields L_{P×Q}(t) = L_P(t) L_Q(t), so Ehrhart quasi-/polynomials multiply under Cartesian product (Beck & Robins, 2007).

3. Binomial generating-function identities

For fixed nonnegative integer d, the identity z^d/(1−z)^{d+1} = ∑_{k≥0} (k choose d) z^k follows by expanding 1/(1−z)^{d+1} via the generalized binomial theorem or combinatorial argument: the coefficient of z^k counts the number of weak compositions of k−d into d+1 parts, which equals (k choose d). Shifting index by d gives the claimed equality (Wilf, 1994; Stanley, 1997).

Dividing both sides by z^d and shifting yields the standard identity 1/(1−z)^{d+1} = ∑_{k≥0} (d + k choose d) z^k, which is the well-known generating function for multiset combinations (hockey-stick identity / stars-and-bars combinatorics).

4. Negative-binomial binomial identity

Use the generalized binomial coefficient definition for arbitrary integer upper argument: for integer r and nonnegative d, C(r,d) = r(r−1)...(r−d+1)/d!. Substitute r = −t + k. Then algebraic manipulation yields

(−1)^d C(−t + k, d) = C(t + d − 1 − k, d).

This equality follows directly from factor-by-factor sign changes in the falling factorial representation and is a standard identity used in combinatorial reciprocity (Graham, Knuth, Patashnik, 1994).

5. Ehrhart series of a bipyramid

Let Q be a polytope containing the origin, and BiPyr(Q) its bipyramid formed by adding vertices ±e_{d+1} scaled appropriately. Counting lattice points in dilates of BiPyr(Q) separates into slices indexed by the last coordinate; the slice at height j corresponds to (t−|j|)Q intersected with the base lattice when |j|≤t and is empty otherwise. Summing contributions over j yields the relation between Ehrhart series

Ehr_{BiPyr(Q)}(z) = (1 + z)/(1 − z) Ehr_Q(z).

The factor (1+z)/(1−z) arises from summing over symmetric integer heights and is detailed in the reconstruction of Theorem 2.4 in Beck & Robins (2007) and Beck’s combinatorial reciprocity arguments.

6. Pick's theorem and a self-intersecting polygon

Consider the polygon P with vertices in order (0,0) → (4,2) → (4,0) → (0,2) → (0,0). This is a self-intersecting "bow-tie" whose signed area computed by the shoelace formula is zero. The lattice boundary points are the union of lattice points on the four segments; enumerating gives B = 7 distinct boundary lattice points. Pick's theorem would assert area = I + B/2 − 1; substituting area = 0 and B = 7 gives I = 1 − 7/2 = −5/2, impossible since interior lattice points I must be a nonnegative integer. Thus Pick's theorem fails for self-intersecting polygons; Pick's theorem requires a simple (non-self-intersecting) polygon (Pick, 1899; Beck & Robins, 2007).

Conclusion. The problems above illustrate central Ehrhart methods: explicit floor/ceil formulas in dimension one, area-and-boundary computations in dimension two, multiplicativity under Cartesian products, classical generating-function combinatorics, negative-binomial identities, and structural constraints needed for Pick's theorem. The formulas and proofs presented are standard and can be found with further detail in the cited literature.

References

  • Beck, M., & Robins, S. (2007). Computing the Continuous Discretely: Integer-point Enumeration in Polyhedra. Springer. (Beck & Robins)
  • Stanley, R. P. (1997). Enumerative Combinatorics, Volume 1. Cambridge University Press.
  • Ehrhart, E. (1967). Sur un problème de géométrie diophantienne linéaire. I. Polyèdres et réseaux. Journal für die reine und angewandte Mathematik, 226, 1–29.
  • Pick, G. (1899). Geometrisches zur Zahlenlehre. Sitzungsberichte des Deutschen Naturwissenschaftlich-Medizinischen Vereines für Böhmen "Lotos" in Prag, 19, 311–319.
  • Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Addison-Wesley.
  • Wilf, H. S. (1994). generatingfunctionology (2nd ed.). Academic Press.
  • Ziegler, G. M. (1995). Lectures on Polytopes. Springer-Verlag.
  • Barvinok, A. (2008). Integer Points in Polyhedra. Zurich Lectures in Advanced Mathematics. EMS.
  • Brion, M., & Vergne, M. (1997). Residue formulae, vector partition functions and lattice points in rational polytopes. Journal of the American Mathematical Society, 10(4), 797–833.
  • Beck, M., Haase, C., & Sam, S. (2010). Residues and Ehrhart polynomials. In Integer Points in Polyhedra—Geometry, Number Theory, Algebra, Optimization (pp. 1–20). Contemporary Mathematics, AMS.

Related Assignments