The number of solutions to linear Diophantine equations and multivariate splines

Dahmen, Wolfgang; Micchelli, Charles A.

doi:10.1090/S0002-9947-1988-0951619-X

The number of solutions to linear Diophantine equations and multivariate splines
HTML articles powered by AMS MathViewer

by Wolfgang Dahmen and Charles A. Micchelli

Trans. Amer. Math. Soc. 308 (1988), 509-532

DOI: https://doi.org/10.1090/S0002-9947-1988-0951619-X

PDF | Request permission

Abstract:

In this paper we study how the number of nonnegative integer solutions of $s$ integer linear equations in $n \geqslant s$ unknowns varies as a function of the inhomogeneous terms. Aside from deriving various recurrence relations for this function, we establish some of its detailed structural properties. In particular, we show that on certain subsets of lattice points it is a polynomial. The univariate case ($s = 1$) yields E. T. Bell’s description of Sylvester’s denumerants. Our approach to this problem relies upon the use of polyhedral splines. As an example of this method we obtain results of R. Stanley on the problem of counting the number of magic squares.

References

Harsh Anand, Vishwa Chander Dumir, and Hansraj Gupta, A combinatorial distribution problem, Duke Math. J. 33 (1966), 757–769. MR 201329
E. T. Bell, Interpolated denumerants and Lambert series, Amer. J. Math. 65 (1943), 382–386. MR 9043, DOI 10.2307/2371962
C. de Boor and K. Höllig, $B$-splines from parallelepipeds, J. Analyse Math. 42 (1982/83), 99–115. MR 729403, DOI 10.1007/BF02786872
Wolfgang Dahmen, On multivariate $B$-splines, SIAM J. Numer. Anal. 17 (1980), no. 2, 179–191. MR 567267, DOI 10.1137/0717017
Wolfgang Dahmen and Charles A. Micchelli, Translates of multivariate splines, Linear Algebra Appl. 52/53 (1983), 217–234. MR 709352, DOI 10.1016/0024-3795(83)80015-9
Wolfgang Dahmen and Charles A. Micchelli, Recent progress in multivariate splines, Approximation theory, IV (College Station, Tex., 1983) Academic Press, New York, 1983, pp. 27–121. MR 754343
Wolfgang Dahmen and Charles A. Micchelli, On the solution of certain systems of partial difference equations and linear dependence of translates of box splines, Trans. Amer. Math. Soc. 292 (1985), no. 1, 305–320. MR 805964, DOI 10.1090/S0002-9947-1985-0805964-6
Wolfgang Dahmen and Charles A. Micchelli, On the local linear independence of translates of a box spline, Studia Math. 82 (1985), no. 3, 243–263. MR 825481, DOI 10.4064/sm-82-3-243-263

Subdivision algorithms for the generation of box spline surfaces

1

A. J. Hoffman and J. B. Kruskal, Integral boundary points of convex polyhedra, Linear inequalities and related systems, Annals of Mathematics Studies, no. 38, Princeton University Press, Princeton, N.J., 1956, pp. 223–246. MR 0085148
Percy A. MacMahon, Combinatory analysis, Chelsea Publishing Co., New York, 1960. Two volumes (bound as one). MR 0141605
John Riordan, An introduction to combinatorial analysis, Wiley Publications in Mathematical Statistics, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0096594
Richard P. Stanley, Combinatorics and commutative algebra, Progress in Mathematics, vol. 41, Birkhäuser Boston, Inc., Boston, MA, 1983. MR 725505, DOI 10.1007/978-1-4899-6752-7
Richard P. Stanley, Linear Diophantine equations and local cohomology, Invent. Math. 68 (1982), no. 2, 175–193. MR 666158, DOI 10.1007/BF01394054
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112