The Horus Sekhemib Perenmaat is another mysterious sovereign of the Second dynasty.
There is no monument which can be assigned to him in Abydos, Saqqara or in any other place of Egypt.
Indeed all the inscriptions with his serekh have been found in Abydos (Umm el Qaab P, the tomb of Peribsen, or in this latter king's funerary enclosure, the 'Middle Fort'), and at Saqqara (8 fragments of stone vessels from the Step Pyramid complex, in the debris out of the eastern galleries VI- VII); a seal impression has also been found in the Old Kingdom town debris of Elephantine (see Leclant - Clerc, Orientalia 62, 1993 p. 250; T. A. H. Wilkinson, Early Dynastic Egypt, 1999 p. 90-91; W. Kaiser, J.P. Pätznick et al., in: MDAIK 55, 1999, 166-172).

The later king list univoquely hand down a lacuna (hwdjefa) before Khasekhemwy (Bebty, Djadjatepy) only citing the Memphite kings of this period and always omitting Peribsen and Sekhemib (see pictures below).

Various hypotheses have been advanced about Horus Sekhemib in relation with Seth Peribsen.
Petrie initially confused the two kings thinking they were the same person/names ('Royal Tombs...' II, 1901 p. 31); Griffith expressed his doubts about Pertie's view in the same publication (R.T. II p. 53 n.49). Effectively, the seal which Petrie cited (loc.cit.) as showing the name Sekhemab Perabsen, was instead inscribed as king Sekhemib Perenmaat.
It was then proposed that Sekhemib was the name of Peribsen in the earlier part of his reign, before the change of the tutelary god atop the serekh from Horus to Seth.
R. Weill ('IIe et IIIe Dynastie' 1908 p. 119-26) was the first to advance the hypothesis of two different kings.
J. Saint Fare Garnot reproposed the identity of the two names for the same individual (B.I.E. 37 p. 317ff; for other articles on the 'Seth rebellion': Newberry A.E. 7, 40ff; Cerny in Grdseloff, ASAE 44, 279ff).
Lacau and Lauer (Pyr. Deg. IV,2 p.43) stressed the similarity of the late 2nd dynasty names based on the verb 'Prj' (Peribsen, Perenmaat, Perenka) and that of Sekhemib's inscriptions Inj Khaswt with Peribsen's Inj Stjet (also cfr. G. Godron, B.I.F.A.O. 57 p. 150ff and B. Gunn A.S.A.E. 28 p. 156 n.4 for the names of Peribsen, Sekhemib).
Wildung and later Barta (respect. in 'Die Rolle...' 1969 and in Z.A.S. 108, 1981) have embraced the theory of the respective equivalence of Sekhemib with Uneg and Peribsen with Sened.
We have discussed, in Sened 's page, that this theory is untenable for various motives:
Shery's inscriptions from Saqqara B3 (Kaiser in G.M. 122, 1991) do not couple Peribsen and Sened as they were one king; furthermore Peribsen's nswt bity can't be Sened, because 'Peribsen' is attested as nswt-bity name too.

More recently there seems to be a tendency to favour the succession Peribsen - Sekhemib - Khasekhem; the inscriptions on clay seals of Sekhemib have all been found in Peribsen's structures at Abydos, and so, like the cases of Qa'a and Hotepsekhemwy, Khasekhemwy and Netjerykhet, egyptologists think that Sekhemib celebrated his predecessor's burial; certainly Sekhemib didn't reign more than few years, and strangely enough, his tomb at Abydos hasn't been located yet (assuming there was one) after more than a century of excavations in the area.

Another possibility could be that Peribsen changed his name (contrarily to what was proposed almost a century ago) from Seth Peribsen to Horus Sekhemib. There's no proof, neither in favour nor contra, this theory.

Some inscriptions on stone vessels of Sekhemib have been found at Saqqara, in the Step Pyramid complex of Netjerykhet (Djoser): the 8 fragments (see picture above) were all found in the debris of Djoser's substructures, outside the galleries VI and VII where most of the earlier kings' inscribed vessels came from.
No Second Dynasty object/text with Peribsen's name has ever been found in all Saqqara.
Together with the evidence of the Abydos seal impressions, this is another indication which must be taken into great account for resolving the problem of the succession Peribsen - Sekhemib.
Peribsen's material might have been voluntarily excluded from Djoser's giant mass of stone vessels, because this king was already considered a kind of herethic for the choice of Seth as his tutelary god; but the later cult attested in the first half of the Fourth Dynasty (performed by Shery who directed the wab priests of Peribsen in the funerary chapel of Sened at Saqqara) seems to contradict the possibility of an early damnatio memoriae for Peribsen (and seal impressions of Khasekhemwy in the eastern galleries could signify that the later vessels found in the Step Pyramid had been taken from the funerary provisions for Khasekhemwy: the 2 clay seals were infact from the ropes which closed the sacks containing these vessels; so Djoser was reusing vessels previously gathered for Ninetjer's and for Khasekhemwy's funerary estabilishments (and possibly from Horus Za 's; cfr. W. Helck in Z.A.S. 106, 1979).

One vessel of Khasekhem was found in the gallery 7 ! So this could mean that the lack of stone vessels was due to the lack of private tombs at Saqqara in the reign of Peribsen.
This is not astonishing, because we know that the royal court, which was moved from This (Abydos) to Memphis (Saqqara cemetery) at the beginning of the Second Dynasty, must have suffered some troubles probably causing the contemporary reigns of local ephemeral king in Memphis (Wneg, Sened, Nwbnefer, Neferkasokar ...) and others in This and Hierakonpolis (the last two or three kings of the Second Dynasty).
Khasekhem, who's credited as the reunificator of the country, initially resided in Nekhen (Hierakonpolis) from where he moved towards Memphis in the second half (or later part ?) of his reign (changing name into Khasekhemwy).

The similarity of Khasekhemwy's horizontal inscription (n.95) from the South tomb of Djoser complex with those of Sekhemib (who anyway still retains in other inscriptions the vertical grouping recalling Peribsen's vessels' inscriptions from Abydos), as well as the use of the falcon topped serekh, united with the other elements discussed above and below, lead us to propend for the supposition of Sekhemib shortly reigning between Peribsen and Khasekhem(wy).

We are unable to trace the history of the events of the later part of the Second Dynasty; from Sethe, Newberry and, to some degree, up to Weill (Ire dyn. 1961), the myth of Horus and Seth had been interpreted as originating from the historical events of the crisis and 'heresy' which had brought Seth Peribsen to the throne.
We have no proof of antagonism between Khasekhemwy and Peribsen; their burials are both in the same necropolis of Umm el Qaab, although on the opposite northern and southern limits; Khasekhemwy built the Shunet ez Zebib few meters south of (the southern wall of) Peribsen's 'Middle Fort'...
Tomb P and V have a roughly similar NW orientation; Dreyer and co. have shown that the earliest stage of tomb V, before the northwards and southwards expansions, must have closely resembled Peribsen's tomb P original layout.

Peribsen is not attested by contemporary inscriptions out of Abydos, Bet Khallaf, Elephantine.
He would have been a southern ruler, perhaps contemporary to the cited Memphite ones; Khasekhem, who had resided in Hierakonpolis, was buried in Abydos, but he might have had other larger tombs at Hierakonpolis (as king Khasekhem) and West Saqqara (as Khasekhemwy, in the second part of his reign): Gisr el Mudir, Western massif of Djoser's complex (?), tomb (Mariette) A4 (Lions tomb) = Djoser's north court storerooms; the unpublished mastaba S3034 in North Saqqara also produced a seal impression of this king similar to IAF 291 (Helck, op. cit).

Therefore Khasekhemwy certainly returned to Saqqara necropolis, and to the Memphite royal court, maybe after defeating (?) local weak sovereigns: there are the archaeological proofs of his presence in the necropolis; the scarcity of these proofs must be attributed to the fact that only in the last years of Khasekhemwy 's reign the court was re-moved to Memphis and also to the unappropriate excavation of the Northern Necropolis of Saqqara, the galleries under the Western Massif and, above all, the Western Saqqara giant stone-enclosure 'Gisr el Mudir'.

But how do we explain Sekhemib's attestations at Saqqara ?
Lacking further evidence we must conclude that Sekhemib might have already attempted (perhaps succeeding in) a returning to Memphis; the vessels found beneath the Step Pyramid unlikely come from the south; it's possible that they were taken by Djoser or by Khasekhemwy from one or more yet unnkown elite tombs of North Saqqara, where they had been the royal gift of Sekhemib to a dead official of his; the 'anarchy' period of split reigns in the north and south of Egypt would have lasted only for the reign of Peribsen (which overlapped those of Ninetjer's Memphite ephemeral successors). No vessels' fragment with Sekhemib inscription has ever been found at Abydos.
J. van Wetering has recently tentatively proposed the attribution to Peribsen of the L-shaped/ Ptahhotep enclosure, west of Djoser Step Pyramid complex; as for the Gisr el Mudir (or even less than for this), there are very few clues to substantiate this statement (on archaeological grounds), but other considerations -which point to exclude for these monuments a later (e.g. Third Dynasty) origin- make this hypothesis an attractive one. Alternatively it could be speculatively proposed the same Sekhemib as the owner of this monument (from which the inscribed stone vessels found in Djoser complex would be possibly originated); the Ptahhotep enclosure seems both smaller and more disturbed (by later tombs and modern activity -it was also the set of a movie-) than Gisr el-Mudir: it is hoped that the Polish excavations in that area can shed light on this structure, its rough datation and eventually its ownership.

The similarity of the names Peribsen and Sekhemib Perenmaat (both with prj and jb) might be a propaganda device of the latter king to asses his reconciliation with Maat (who had not been respected by the predecessor) and the return of Horus as king protecting god.
Or, as already said, it could point towards the hypothesis of a succession of the names Peribsen > Sekhemib, thus being a clue of Peribsen's failure and his consequent change of name and titulary during the latest part of his reign.

Up to now the most important suggestion for the succession of Peribsen and Sekhemib have been done by Jean Pierre Pätznick in relation to the seal impressions from Elephantine (cf. MDAIK reports espec.: MDAIK 55, 1999, 166-173 and MDAIK 51, 1995, 179-184). The epigraphic and palaeographic studies seems to indicate that Seth (or Ash) Peribsen preceded Horus Sekhemib (probably a completely different ruler); these criterions may be also applied to the study of the inscriptions incised on Stone Vessels, which also appear to favour the succession Peribsen - Sekhemib - Khasekhem, especially when the horizontal inscriptions of Sekhemib are confronted with Khasekhem(wy)'s ones.
About the patron deity, Pätznick favours Ash rather than Seth as commonly reported; I think that there was a strict relationship between these two gods and their functions in the Early Dynastic; perhaps the Second Dynasty name of Seth (spelled "Suthesh") might have been originated from the syncretistic fusion of the two deities Seth and Ash (Sethesh) but it's actually impossible to demonstrate this speculative statement of mine (even in linguistical terms).

For the causes of these religious-titulary anomalies (but also consider the Nebwy of Merbiape Adjib, a falconless serekh of Sneferka, and the later Horus Seth Khasekhemwy) and chronological discussions see under Peribsen.
For discussions on the Seal impressions of Sekhemib see Peter Kaplony I.A.F. I, II, III (figures) 1963.
Abydos Seal impressions in I.A.F. III are from Petrie R.T. II pl. 21 n. 164- 172 (with some slight divergencies in the drawing), and from E. Naville- E. Peet - H. Hall, 'The Cemeteries of Abydos' pt. I, 1914 pl. 9.
No stone vessel of Sekhemib has been found at Abydos; Spencer's (Early Dynastic Objects in the British Museum) n. 277 is unprovenanced and said to be probably from Abydos.
All the 8 inscribed stone vessels from the Step Pyramid complex in Lacau-Lauer Pyr.Deg. IV n. 87-94 (pl. 18) had been already published by B. Gunn, A.S.A.E. 28 pl. 2 and by Firth - Quibell, Step Pyramid II pl. 88- 89.
The inscriptions of Sekhemib up to 1993 are listed in the Quellenlist of Jochem Kahl (Das System der Agyptische Hieroglyphenschrift Dyn. 0-3, 1994 p. 355-6 n. 2864- 2886) where this king is placed before Peribsen (p. 7,8).
The seal impressions of Sekhemib in Peribsen's tomb and enclosure (Middle Fort) of Abydos indicates that the former was buried in another yet unexplored area of the Thinite necropolis or perhaps in another quite different site.

UPDATE (13-10-2004)
A fragmentary seal impression with Sekhem(ib)-Perjen(-Maat) Horus name has been found in the Umm el-Qaab tomb of Khasekhemwy (V, on sack-sealings from rooms 31-33, directly north of the burial chamber), a fact that further reinforces the direct succession Sekhemib > Khasekhem(ui) at the end of the dynasaty (cf. Dreyer, in: MDAIK 59, 2003, 115, pl. 24b).