{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:40:01Z","timestamp":1750455601389,"version":"3.41.0"},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"1-2","license":[{"start":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T00:00:00Z","timestamp":1108425600000},"content-version":"unspecified","delay-in-days":45,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>For fixed positive integers <jats:inline-formula>$k,q,r$<\/jats:inline-formula> with <jats:inline-formula>$q$<\/jats:inline-formula> a prime power and large <jats:inline-formula>$m$<\/jats:inline-formula>, we investigate matrices with <jats:inline-formula>$m$<\/jats:inline-formula> rows and a maximum number <jats:inline-formula>$N_q (m,k,r)$<\/jats:inline-formula> of columns, such that each column contains at most <jats:inline-formula>$r$<\/jats:inline-formula> nonzero entries from the finite field <jats:inline-formula>$GF(q)$<\/jats:inline-formula> and any <jats:inline-formula>$k$<\/jats:inline-formula> columns are linearly independent over <jats:inline-formula>$GF(q)$<\/jats:inline-formula>. For even integers <jats:inline-formula>$k \\geq 2$<\/jats:inline-formula> we obtain the lower bounds <jats:inline-formula>$N_q(m,k,r) = \\Omega (m^{kr\/(2(k-1))})$<\/jats:inline-formula>, and <jats:inline-formula>$N_q(m,k,r) = \\Omega (m^{((k-1)r)\/(2(k-2))})$<\/jats:inline-formula> for odd <jats:inline-formula>$k \\geq 3$<\/jats:inline-formula>. For <jats:inline-formula>$k=2^i$<\/jats:inline-formula> we show that <jats:inline-formula>$N_q(m,k,r) = \\Theta ( m^{kr\/(2(k-1))})$<\/jats:inline-formula> if <jats:inline-formula>$\\gcd(k-1,r) = k-1$<\/jats:inline-formula>, while for arbitrary even <jats:inline-formula>$k \\geq 4$<\/jats:inline-formula> with <jats:inline-formula>$\\gcd(k-1,r) =1$<\/jats:inline-formula> we have <jats:inline-formula>$N_q(m,k,r) = \\Omega (m^{kr\/(2(k-1))} \\cdot (\\log m)^{1\/(k-1)})$<\/jats:inline-formula>. Matrices which fulfil these lower bounds can be found in polynomial time. Moreover, for <jats:inline-formula>$\\Char (GF(q)) &gt; 2 $<\/jats:inline-formula> we obtain <jats:inline-formula>$N_q(m,4,r) = \\Theta (m^{\\lceil 4r\/3\\rceil\/2})$<\/jats:inline-formula>, while for <jats:inline-formula>$\\Char (GF(q)) = 2$<\/jats:inline-formula> we can only show that <jats:inline-formula>$N_q(m,4,r) = O (m^{\\lceil 4r\/3\\rceil\/2})$<\/jats:inline-formula>. Our results extend and complement earlier results from [7, 18], where the case <jats:inline-formula>$q=2$<\/jats:inline-formula> was considered.<\/jats:p>","DOI":"10.1017\/s0963548304006625","type":"journal-article","created":{"date-parts":[[2005,2,15]],"date-time":"2005-02-15T12:56:08Z","timestamp":1108472168000},"page":"147-169","source":"Crossref","is-referenced-by-count":2,"title":["Sparse Parity-Check Matrices over ${GF(q)}$"],"prefix":"10.1017","volume":"14","author":[{"given":"HANNO","family":"LEFMANN","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2005,2,15]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548304006625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,20]],"date-time":"2025-06-20T21:16:22Z","timestamp":1750454182000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548304006625\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":0,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["S0963548304006625"],"URL":"https:\/\/doi.org\/10.1017\/s0963548304006625","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"type":"print","value":"0963-5483"},{"type":"electronic","value":"1469-2163"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}