It is shown that there exists no quasi-symmetric 2-(33,15,35) design with intersection numbers 6 and 9. This is proved by considering the ternary code generated by the incidence vectors of the blocks and its dual code.
Introduction
A 2-(v,k,λ) design D is a pair consisting of a set P of v points and a collection B of k-element subsets of P (called blocks) such that every 2-element subset of P is contained in exactly λ blocks. The number of blocks that contain a given point is traditionally denoted by r, and the total number of blocks is b. We assume that 2<k<v throughout this paper. A design with no repeated block is called simple. In this paper, we consider only simple designs. Often a 2-(v,k,λ) design is simply called a 2-design. A 2-design can be represented by its (block by point) incidence matrixA=(aij), where aij=1 if the jth point is contained in the ith block and aij=0 otherwise.
A 2-design is called quasi-symmetric if the number of points in the intersection of any two distinct blocks takes only two values x and y (x<y). The values x and y are called the intersection numbers. Quasi-symmetric 2-designs are closely related to strongly regular graphs and codes (see, e.g., [2, 13, 14]). Four classes of quasi-symmetric 2-designs were given in [8], namely, multiples of symmetric 2-designs, Steiner systems with v>k2, strongly resolvable 2-designs and residual designs of biplanes. A quasi-symmetric 2-design D is called exceptional if neither D nor its complementary design belongs to one of these four classes. It is a fundamental problem to determine whether there exists an exceptional quasi-symmetric 2-design for a given set of parameters. The feasible parameters of exceptional quasi-symmetric 2-(v,k,λ) designs with 2k≤v≤70 are listed in [12 Table 48.25]. Codes have been used to investigate these existence problems (see, e.g., [3], [4], [6] and [7]). For recent nonexistence results based on restrictions on block graphs, see [9] and [10].
The existence of a quasi-symmetric 2-(33,15,35) design is listed as an open question in [12 Table 48.25] (see also [2 Section 8.5.6]). Such a design necessarily has intersection numbers 6 and 9 (see [2 Section 8.5.6]). Among the parameter sets for exceptional quasi-symmetric designs listed as unresolved in that reference, this one has the smallest number of points. The aim of this paper is to establish the following theorem.
Theorem 1.There exists no quasi-symmetric 2-(33, 15, 35) design.
Remark 2. If such a design existed, its block graph, in which two distinct blocks are adjacent if and only if they intersect in exactly 9 points, would be a strongly regular graph with parameters (176, 45, 18, 9). Strongly regular graphs with these parameters are known to exist (see [1]).
Preliminaries
Our approach is to consider the ternary code generated by the incidence vectors of the blocks of a hypothetical design, together with its dual code. In this section, we introduce the notation and definitions used in the proof. Throughout the paper, the ring or field in which a calculation is performed is understood from the context. We specify it explicitly whenever necessary to avoid ambiguity.
Ternary codes
Let F3={0,1,2} denote the finite field of order 3. A ternary codeC of length n is a vector subspace of F3n. A vector of C is called a codeword of $C.
The weightwt(x) of a vector x∈F3n is the number of nonzero components of x.
The dual code C⊥ of a ternary code C of length n is defined as follows:
C⊥={x∈F3n∣x⋅y=0for all y∈C},
where
x⋅y=i=1∑nxiyi
for x=(x1,x2,…,xn) and y=(y1,y2,…,yn)∈F3n. A ternary code C is called self-orthogonal if C⊆C⊥.
Maps and inner product
We employ the following maps and inner product. Define a map ϕ:F3→Z by
ϕ(0)=0,ϕ(1)=1andϕ(2)=−1.
Let ρ:Z→F3 denote the reduction map modulo 3. Then
ρ(ϕ(a))=a
for every element a∈F3. We extend both maps coordinatewise to vectors and use the same symbols for these extensions. Thus, for u=(u1,u2,…,un)∈F3n and for z=(z1,z2,…,zn)∈Zn, we write
ϕ(u)=(ϕ(u1),ϕ(u2),…,ϕ(un))∈Zn
and
ρ(z)=(ρ(z1),ρ(z2),…,ρ(zn))∈F3n.
In particular, ρ(ϕ(u))=u for every vector u∈F3n. For vectors a=(a1,a2,…,an) and b=(b1,b2,…,bn)∈Zn, define their integer inner product by
⟨a,b⟩Z=i=1∑naibi.
Proof of Theorem 1
The aim of this section is to give a proof of Theorem 1 that is as elementary as possible.
Ternary code associated with the design
Suppose that there exists a quasi-symmetric 2-(33, 15, 35) design D=(X,B) with intersection numbers 6 and 9. We may assume that X={1,2,…,33}. For each subset W⊆X, let W∈{0,1}33 denote its characteristic vector.
Let A be the 176×33 incidence matrix of D. Then the (B,p)-entry of A is 1 if p∈B and 0 otherwise, and the row indexed by B is B. Since r=80 and λ=35, we have
ATA=45I33+35J33andB∈B∑B=801(1)
over Z, where AT denotes the transpose of A, I33 is the identity matrix of order 33, J33 is the 33×33 all-ones matrix and 1 denotes the all-ones vector of length 33.
Let C(D) be the ternary code generated by the rows of A, that is,
C(D)=⟨B∣B∈B⟩⊆F333.
The 176×176 integer matrix AAT has diagonal entries 15 and off-diagonal entries 6 or 9, since D has intersection numbers 6 and 9. Since all these entries are divisible by 3, we have AAT≡O(mod3), where O is the 176×176 zero matrix. Thus, C(D) is self-orthogonal. Reducing the second equality in (1) modulo 3, we obtain
C(D)∋B∈B∑B=21.
It follows that
1∈C(D)⊆C(D)⊥.(2)
Restrictions on (0, 1)-vectors in C(D)⊥
Let u=(u1,u2,…,u33)∈C(D)⊥. For each block B∈B, let
Proof. Since ρ is additive and ρ(ϕ(a))=a for every element a∈F3, we have
ρ(SB)=p∈B∑up=p=1∑33up(B)p=u⋅B=0
for each block B∈B. Here, (B)p denotes the pth coordinate of B. The last equality follows from u∈C(D)⊥ and B∈C(D). Thus, SB is divisible by 3 for every block B∈B.
Since r=80, we have
B∈B∑SB=p=1∑33ϕ(up)∣{B∈B∣p∈B}∣=80t(u).
The entry of Aϕ(u)T indexed by B is SB. From (1), we obtain
The last equality follows from ϕ(0)=0 and ϕ(1)2=ϕ(2)2=1. This completes the proof.
For use in the following lemma, note that
SB=p∈B∑ϕ(up)=⟨ϕ(u),ϕ(B)⟩Z
for every vector u∈C(D)⊥ and B∈B.
Lemma 4. Suppose that u∈C(D)⊥ and that ϕ(u) has 6 entries equal to 1, 3 entries equal to −1 and 24 entries equal to 0. Then
SB∈{0,3}
for every block B∈B.
Proof. Since ϕ(u) has 6 entries equal to 1, 3 entries equal to −1 and all remaining entries equal to 0, and SB=⟨ϕ(u),ϕ(B)⟩Z, we have −3≤SB≤6. By Lemma 3, we have SB∈3Z. It follows that
SB∈{−3,0,3,6}.
Thus, for every block B∈B, we have
SB(SB−3)≥0,
with equality if and only if SB∈{0,3}. Moreover, since wt(u)=9 and t(u)=3, Lemma 3 gives
B∈B∑SB=240
and
B∈B∑SB2=45⋅9+35⋅32=720.
Hence, we have
B∈B∑SB(SB−3)=720−3⋅240=0.
Therefore, we conclude that SB∈{0,3} for every block B∈B. □
We now apply Lemma 3 to characteristic vectors of subsets of X. Suppose that W⊆X satisfies W∈C(D)⊥. Let u=W and w=∣W∣. The vector u is a (0,1)-vector of weight w. Since ϕ(0)=0 and ϕ(1)=1, we have
t(u)=p=1∑33ϕ(up)=w.
Moreover, we have
SB=p∈B∑ϕ(up)=∣B∩W∣.
for each block B∈B. By Lemma 3, SB=∣B∩W∣ is divisible by 3. Since ∣B∣=15, we also have
0≤∣B∩W∣≤min(w,15).
Let
Iw={i∈3Z∣0≤i≤min(w,15)}.
Thus, ∣B∩W∣∈Iw for every B∈B. For each i∈Iw, define
ni=∣{B∈B∣∣B∩W∣=i}∣.(4)
Thus, ni is the number of blocks meeting W in exactly i points.
Since
ni=∣{B∈B∣∣B∩W∣=i}∣=∣{B∈B∣SB=i}∣,
each block is counted exactly once in ∑i∈Iwni. Thus, we have
i∈Iw∑ni=∣B∣=176.(5)
For each i∈Iw, the ni blocks with SB=i contribute ini to ∑B∈BSB and i2ni to ∑B∈BSB2. Hence, we obtain
Thus, wt(x) is divisible by 3. Since 1∈C(D)⊆C(D)⊥ by (2) and x∈C(D)⊥, the linearity of C(D)⊥ gives 1+2x∈C(D)⊥. Moreover, since x is a (0,1)-vector, we have
1+2x∈{0,1}33 and wt(1+2x)=33−wt(x).
Therefore, it suffices to rule out weights wt(x)=3, 6, 9 and 12. We consider these weights in the order wt(x)=3, 9, 6 and 12, since the later cases use the exclusions established in the earlier ones.
(i) Suppose that wt(x)=3. Take u=x in Lemma 3. Then, since x is a (0,1)-vector, we have wt(u)=t(u)=3 and 0≤SB≤3 for every block B∈B. Since SB is divisible by 3, we have SB∈{0,3}. In either case, SB2=3SB.
(iii) Suppose that wt(x)=6. Write x=W, where W⊆X and ∣W∣=6. Let n0, n3 and n6 be as defined in (4). From (7), we have
n0+n3+n6=176,
3n3+6n6=480
and
9n3+36n6=1530.
This gives 18n6=90. Since n6>0, there is a block B∈B with ∣B∩W∣=6. Hence, we have W⊆B. By the definition of C(D) and (2), we have B∈C(D)⊆C(D)⊥. Since W=x∈C(D)⊥ by the assumption, we have
B+2W=B∖W∈C(D)⊥∩{0,1}33
and
wt(B∖W)=15−6=9.
This contradicts the exclusion of weight 9 established above.
(iv) Suppose that wt(x)=12. Write x=W, where W⊆X and ∣W∣=12. Let n0, n3, n6, n9 and n12 be as defined in (4). From (7), we have
First suppose that n12>0. Then there is a block B∈B with W⊆B. As in the case wt(x)=6, we have B∈C(D)⊆C(D)⊥ and W∈C(D)⊥. It follows that
B+2W=B∖W∈C(D)⊥∩{0,1}33
and
wt(B∖W)=15−12=3.
This contradicts the exclusion of weight 3 established above. Hence, we have n12=0.
Now suppose that n9>0. Choose a block B∈B with ∣B∩W∣=9. Let
u=B+2W∈C(D)⊥.
Since ∣B∖W∣=6 and ∣W∖B∣=3, the vector ϕ(u) has 6 entries equal to 1, 3 entries equal to −1 and 24 entries equal to 0. By Lemma 4, we have
⟨ϕ(u),ϕ(B)⟩Z∈{0,3}.
On the other hand, since u=B+2W∈F333, we have up=1 for p∈B∖W and up=1+2=0 for p∈B∩W. Thus, we have ϕ(up)=1 for p∈B∖W and ϕ(up)=0 for p∈B∩W. Hence, we obtain
⟨ϕ(u),ϕ(B)⟩Z=p∈B∑ϕ(up)=∣B∖W∣=15−9=6,
a contradiction. Therefore, we have n9=0.
From (9), we have n0=6. Thus, there is a block B∈B with B∩W=∅. As in the case wt(x)=6, we have B,W∈C(D)⊥. From (2), we have 1∈C(D)⊥. It follows that
1+2B+2W=X∖(B∪W)∈C(D)⊥∩{0,1}33
and
wt(X∖(B∪W))=33−15−12=6.
This contradicts the exclusion of weight 6 established above.
This completes the proof.
Identity for a ternary code and its dual code
For a ternary code C of length 33, define
S(C)=x∈C∩{0,1}33∑(−1)wt(x)(33−2wt(x)).
The following identity can be derived from the MacWilliams identity for complete weight enumerators (see, e.g., [5 Theorem 2.3.2]) by specialization and differentiation, together with the assumptions 1∈C⊆C⊥. A direct proof of Lemma 6 using character sums is given in Appendix A.
Lemma 6. Let C be a ternary code of length 33. Suppose that 1∈C⊆C⊥. Then
S(C⊥)=−∣C∣316S(C).(10)
Proof of Theorem 1
For a ternary code C of length 33, define the following:
B(C)=C∩{0,1}33.
We are ready to give a proof of Theorem 1.
Proof of Theorem 1. Suppose that there exists a quasi-symmetric 2-(33, 15, 35) design D with intersection numbers 6 and 9. We apply the preceding lemmas to the ternary code C(D).
Let E be either C(D) or C(D)⊥. From (2), we have C(D)⊆C(D)⊥. Thus, we have E⊆C(D)⊥ in either case. If x∈B(E), then by Lemma 5 we have
wt(x)∈{0,15,18,33}.
Let 0 denote the zero vector. From (2), we have 1∈E. Thus, we have 0,1∈B(E). Hence, B(E) contains exactly one vector of weight 0 and exactly one vector of weight 33. Therefore, the total contribution of these two vectors to S(E) is
1⋅(−1)0(33−0)+1⋅(−1)33(33−66)=33+33=66.(11)
For every vector x∈B(E), we have 1+2x∈E. Since x is a (0,1)-vector, we have
1+2x∈B(E)andwt(1+2x)=33−wt(x).
The map x↦1+2x is its own inverse, and hence is a bijection on B(E). It maps the vectors of weight 15 to those of weight 18, and conversely. Define
a15(B(E))=∣{x∈B(E)∣wt(x)=15}∣.
Therefore, B(E) contains exactly a15(B(E)) vectors of each of these two weights.
The characteristic vectors of the 176 distinct blocks of D are distinct codewords of weight 15 in C(D) whose entries are all 0 or 1. Since C(D)⊆C(D)⊥, they also belong to C(D)⊥. Consequently, we have
On the other hand, since (2) gives 1∈C(D)⊆C(D)⊥, by Lemma 6 we have
S(C(D)⊥)=−∣C(D)∣316S(C(D)).
Since ∣C(D)∣>0 and S(C(D))<0, the right-hand side is positive, contradicting S(C(D)⊥)<0. Therefore, no such design exists. This completes the proof of Theorem 1. □
Other parameter sets
Finally, we consider other parameter sets for exceptional quasi-symmetric designs.
Among those listed as unresolved in [2 Section 8.5.6], the two with the smallest numbers of points, excluding the case settled by Theorem 1, are those of a 2-(35,14,13) design with intersection numbers 5 and 8 and a 2-(39,12,22) design with intersection numbers 3 and 6.
The former is ruled out by a recent result of Shpectorov and Zhao [11]. Indeed, its block graph, in which two blocks are adjacent when they intersect in 8 points, would be strongly regular with parameters (85,14,3,2), contrary to their nonexistence theorem. Together with Theorem 1, this leaves the case of a quasi-symmetric 2-(39,12,22) design with intersection numbers 3 and 6 as the smallest remaining case.
The ternary code approach used in this paper can also be considered for quasi-symmetric 2-(v,k,λ) designs with intersection numbers x and y satisfying
k≡x≡y≡0(mod3)andr=0(mod3).
A 2-(39,12,22) design with intersection numbers 3 and 6 satisfies these conditions, where r=76. However, the present argument does not establish its nonexistence. Indeed, suppose that such a design D exists, and let C(D) be its ternary code generated by the rows of the incidence matrix of D. Since k≡x≡y≡0(mod3), the code C(D) is self-orthogonal. Moreover, since r=0(mod3), C(D) contains the all-ones vector. Define
S39(C(D))=z∈C(D)∩{0,1}39∑(−1)wt(z)(39−2wt(z)),
and define S39(C(D)⊥) similarly. The same calculation as in Appendix § 5 gives
The coefficient is positive, so this identity does not force S39(C(D)⊥) and S39(C(D)) to have opposite signs. Thus, the final sign argument used in our proof does not yield a contradiction. The present approach may also be useful in studying the nonexistence of a quasi-symmetric 2-(45,18,34) design with intersection numbers 6 and 9.
Acknowledgments. This work was supported by JSPS KAKENHI Grant Numbers 23K25784 and 25K21995.
Use of generative AI. The author used OpenAI’s ChatGPT (GPT-6 Astra) to assist in developing the proofs of Theorem 1 and the supporting lemmas in November 2026. The author independently verified all mathematical arguments presented in the paper.
Proof of the duality identity
In this appendix, we give a direct proof of Lemma 6 using character sums.
Proof of Lemma 6. Let ω∈C be a primitive cube root of unity, so that
ω3=1,ω=1 and 1+ω+ω2=0.
For an element γ∈F3, define ωγ=ωϕ(γ). Since ω3=1, this value is independent of the choice of an integer representative of γ. For γ,δ∈F3, we have
ωγ+δ=ωγωδ,
since ϕ(γ+δ)≡ϕ(γ)+ϕ(δ)(mod3) and ω3=1.
For a vector x∈F333, we have
∣C∣1u∈C∑ωu⋅x={10if x∈C⊥,if x∈/C⊥.(13)
Indeed, if x∈C⊥, then ∑u∈Cωu⋅x=∣C∣. If x∈/C⊥, choose u0∈C with u0⋅x=0, and let
Qx=u∈C∑ωu⋅x.
Since the map u↦u+u0 is a bijection on C, we have
Qx=u∈C∑ω(u+u0)⋅x=ωu0⋅xQx.
Since ωu0⋅x=1, it follows that Qx=0. This proves (13).
Since m2 is divisible by 3, we have ω2m2=1. Since m0=0, we have m1+m2=33. Substituting z=−1 into Hu(z) and using (16) together with ω2m2=1, we obtain
Since m0=0, every coordinate of u is either 1 or 2. Thus, none of the factors of Hu(z) vanishes at z=−1. Hence, Hu(z)=0 in a neighbourhood of −1. By the product rule, we have
Hu′(z)=p=1∑33ωup1≤q≤33q=p∏(1+ωuqz).
Dividing both sides by Hu(z) and cancelling common factors, we obtain
Here, the fourth equality follows from m1+m2=33, and the last equality follows from ω+ω2=−1 and m1−m2=33−2m2.
Since m0=0, the vector u+21 has m1 entries equal to 0 and m2 entries equal to 1. Thus, u+21 is a (0,1)-vector of weight m2. Hence, the definition of f gives
Since 1∈C, the map u↦u+21 sends every codeword of weight 33 in C to a vector of B(C). Conversely, if x∈B(C), then u=x+1 belongs to C and has every coordinate equal to 1 or 2. Thus, we have wt(u)=33. These maps are inverse to each other. Hence, u↦u+21 is a bijection from the set of codewords of weight 33 in C onto B(C). Using this bijection and (20), we obtain
[1]A.E. Brouwer, Parameters of Strongly Regular Graphs, Available online at http://www.win.tue.nl/~aeb/graphs/srg/srg tab.html.
[2]A.E. Brouwer and H. Van Maldeghem, Strongly Regular Graphs, Encyclopedia Math. Appl., 182, Cambridge University Press, Cambridge, 2022.
[3]D. Ghosh, J. Pal and L.K. Dey, The classification of self-orthogonal codes of length 42, Discrete Math. Algorithms Appl. 10 (2018), 1850083, 8 pp.DOI
[4]M. Harada, A. Munemasa and V.D. Tonchev, Self-dual codes and the nonexistence of a quasi-symmetric 2-(37, 9, 8) design with intersection numbers 1 and 3, J. Combin. Des. 25 (2017), 469–476.DOI
[5]F.J. MacWilliams, C.L. Mallows and N.J.A. Sloane, Generalizations of Gleason’s theorem on weight enumerators of self-dual codes, IEEE Trans. Inform. Theory 18 (1972), 794–805.DOI
[6]A. Munemasa and V.D. Tonchev, Ternary codes, biplanes, and the nonexistence of some quasisymmetric and quasi-3 designs, J. Combin. Des. 28 (2020), 745–752.arxiv.org/abs/2003.04453
[7]A. Munemasa and V.D. Tonchev, Quasi-symmetric 2-(41, 9, 9) designs and doubly even self-dual codes of length 40, Appl. Algebra Engrg. Comm. Comput. 33 (2022), 855–866.DOI
[8]A. Neumaier, “Regular sets and quasi-symmetric 2-designs,” in Combinatorial Theory, D. Jungnickel and K. Vedder (Eds.), Lecture Notes in Math. Vol. 969, 1982, pp. 258–275.DOI
[9]R.M. Pawale, M.S. Shrikhande and K.S. Rajbihar, Non-existence of quasi-symmetric designs with restricted block graphs, Des. Codes Cryptogr. 90 (2022), 871–879.DOI
[10]K.S. Rajbihar and R.M. Pawale, Non-existence of quasi-symmetric designs having certain pseudo-geometric block graphs, AKCE Int. J. Graphs Comb. 21 (2024), 120–128.
[11]S. Shpectorov and T. Zhao, Strongly regular graphs with parameters (85, 14, 3, 2) do not exist, J. Combin. Theory Ser. A 225 (2027), 106242.arxiv.org/abs/2504.02449
[12]M.S. Shrikhande, “Quasi-symmetric designs,” in Handbook of Combinatorial Designs (second edition), C.J. Colbourn and J.H. Dinitz (Eds.), Chapman & Hall/CRC, Boca Raton, FL, 2007, pp. 578–582.
[13]M.S. Shrikhande and S.B. Sane, Quasi-Symmetric Designs, London Math. Soc. Lecture Note Ser. 164, Cambridge University Press, Cambridge, 1991.DOI
[14]V.D. Tonchev, “Codes,” in Handbook of Combinatorial Designs (second edition), C.J. Colbourn, J.H. Dinitz (Eds.), Chapman & Hall/CRC, Boca Raton, FL, 2007, pp. 677–702.