{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T20:12:23Z","timestamp":1773087143168,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T00:00:00Z","timestamp":1739836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T00:00:00Z","timestamp":1739836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this note, we study the size of the support of integer solutions to linear equations\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$Ax=b, ~x\\in \\mathbb {Z}^n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo>=<\/mml:mo>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mspace\/>\n                            <mml:mi>x<\/mml:mi>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>Z<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$A\\in \\mathbb {Z}^{m\\times n}, b\\in \\mathbb {Z}^n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>A<\/mml:mi>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>Z<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mrow>\n                                <mml:mi>m<\/mml:mi>\n                                <mml:mo>\u00d7<\/mml:mo>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mi>b<\/mml:mi>\n                            <mml:mo>\u2208<\/mml:mo>\n                            <mml:msup>\n                              <mml:mrow>\n                                <mml:mi>Z<\/mml:mi>\n                              <\/mml:mrow>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msup>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . We give an upper bound on the smallest support size as a function of\n                    <jats:italic>A<\/jats:italic>\n                    , taken as a worst case over all\n                    <jats:italic>b<\/jats:italic>\n                    such that the above system has a solution. This bound is asymptotically tight, and in fact matches the bound given in [1], while the proof presented here is simpler, relying only on linear algebra.\n                  <\/jats:p>","DOI":"10.1007\/s10107-025-02202-7","type":"journal-article","created":{"date-parts":[[2025,2,18]],"date-time":"2025-02-18T07:23:33Z","timestamp":1739863413000},"page":"789-800","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the smallest support size of integer solutions to linear equations"],"prefix":"10.1007","volume":"214","author":[{"given":"Yatharth","family":"Dubey","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3553-9431","authenticated-orcid":false,"given":"Siyue","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,18]]},"reference":[{"issue":"1\u20132","key":"2202_CR1","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s10107-021-01657-8","volume":"192","author":"I Aliev","year":"2022","unstructured":"Aliev, I., Averkov, G., De Loera, J.A., Oertel, T.: Sparse representation of vectors in lattices and semigroups. Math. Program. 192(1\u20132), 519\u2013546 (2022)","journal-title":"Math. Program."},{"issue":"3","key":"2202_CR2","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1137\/17M1162792","volume":"28","author":"I Aliev","year":"2018","unstructured":"Aliev, I., De Loera, J.A., Eisenbrand, F., Oertel, T., Weismantel, R.: The support of integer optimal solutions. SIAM J. Optim. 28(3), 2152\u20132157 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2202_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/BF01393823","volume":"73","author":"E Bombieri","year":"1983","unstructured":"Bombieri, E., Vaaler, J.: On siegel\u2019s lemma. Invent. Math. 73(1), 11\u201332 (1983)","journal-title":"Invent. Math."},{"key":"2202_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G., et al.: Integer programming, vol. 271. Springer (2014)"},{"issue":"1","key":"2202_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0095-8956(86)90064-X","volume":"40","author":"W Cook","year":"1986","unstructured":"Cook, W., Fonlupt, J., Schrijver, A.: An integer analogue of caratheodory\u2019s theorem. J. Comb. Theory, Ser. B 40(1), 63\u201370 (1986)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"2202_CR6","volume-title":"Abstract algebra","author":"DS Dummit","year":"2004","unstructured":"Dummit, D.S., Foote, R.M.: Abstract algebra, vol. 3. Wiley Hoboken (2004)"},{"issue":"5","key":"2202_CR7","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.orl.2005.09.008","volume":"34","author":"F Eisenbrand","year":"2006","unstructured":"Eisenbrand, F., Shmonin, G.: Carath\u00e9odory bounds for integer cones. Oper. Res. Lett. 34(5), 564\u2013568 (2006)","journal-title":"Oper. Res. Lett."},{"key":"2202_CR8","first-page":"240","volume":"2","author":"J Hadamard","year":"1893","unstructured":"Hadamard, J.: Resolution d\u2019une question relative aux determinants. Bull. des sciences math. 2, 240\u2013246 (1893)","journal-title":"Bull. des sciences math."},{"key":"2202_CR9","volume-title":"An introduction to the theory of numbers","author":"GH Hardy","year":"1979","unstructured":"Hardy, G.H., Wright, E.M.: An introduction to the theory of numbers. Oxford University Press, Xx (1979)"},{"key":"2202_CR10","unstructured":"OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences. Published electronically at https:\/\/oeis.org"},{"key":"2202_CR11","doi-asserted-by":"crossref","DOI":"10.1090\/mmono\/134","volume-title":"Problems and theorems in linear algebra","author":"VV Prasolov","year":"1994","unstructured":"Prasolov, V.V.: Problems and theorems in linear algebra, vol. 134. American Mathematical Soc (1994)"},{"key":"2202_CR12","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1998","unstructured":"Schrijver, A.: Theory of linear and integer programming. John Wiley & Sons (1998)"},{"key":"2202_CR13","unstructured":"Seb\u00f6, A.: Hilbert bases, caratheodory\u2019s theorem and combinatorial optimization. In: Proceedings of the 1st integer programming and combinatorial optimization conference, pp. 431\u2013455 (1990)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02202-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02202-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02202-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T07:46:27Z","timestamp":1764575187000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02202-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,18]]},"references-count":13,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["2202"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02202-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,18]]},"assertion":[{"value":"14 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}